biweekly-contest-44

leetcode.com/contest/biweekly-contest-44

Welcome to Biweekly Contest 44! Feel free to share and post your contest experience here!

You can also view the rankings for the contest here.

Links to the individual problems are included below:

Find the Highest Altitude (3 points)

Minimum Number of People to Teach (4 points)

Decode XORed Permutation (5 points)

Count Ways to Make Array With Product (6 points)

1732. Find the Highest Altitude

leetcode.com/problems/find-the-highest-altitude/

Easy

71Add to ListShare

There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

Example 1:

Input: gain = [-5,1,5,0,-7] Output: 1 Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

Example 2:

Input: gain = [-4,-3,-2,-1,4,3,2] Output: 0 Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

Constraints:

n == gain.length
1 <= n <= 100
-100 <= gain[i] <= 100

Let's note that the altitude of an element is the sum of gains of all the elements behind it

Show Hint 2

Getting the altitudes can be done by getting the prefix sum array of the given array

class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        gap = 0
        max_gap = 0
        
        for h in gain:
            gap += h
            max_gap = max(max_gap, gap)
            
        return max_gap

class Solution:
    def largestAltitude(self, A):
        return max([0] + list(accumulate(A)))

[0] + list(accumulate(A))

[0, -5, -4, 1, 1, -6]

1733. Minimum Number of People to Teach

leetcode.com/problems/minimum-number-of-people-to-teach/

Medium

422Add to ListShare

On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

There are n languages numbered 1 through n,
languages[i] is the set of languages the ith user knows, and
friendships[i] = [ui, vi] denotes a friendship between the users ui and vi.

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.

Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn't guarantee that x is a friend of z.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]] Output: 1 Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]] Output: 2 Explanation: Teach the third language to users 1 and 2, yielding two users to teach.

Constraints:

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= ui < vi <= languages.length
1 <= friendships.length <= 500
All tuples (ui, vi) are unique
languages[i] contains only unique values

You can just use brute force and find out for each language the number of users you need to teach

Hide Hint 2

Note that a user can appear in multiple friendships but you need to teach that user only once

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        languages = [set(l) for l in languages]

        dontspeak = set()
        for u, v in friendships:
            u = u-1
            v = v-1
            if languages[u] & languages[v]: continue
            dontspeak.add(u)
            dontspeak.add(v)

        langcount = Counter()
        for f in dontspeak:
            for l in languages[f]:
                langcount[l] += 1

        return 0 if not dontspeak else len(dontspeak) - max(list(langcount.values()))

2
[[1],[2],[1,2]]
[[1,2],[1,3],[2,3]]

print(languages)

[{1}, {2}, {1, 2}]

        dontspeak = set()
        for u, v in friendships:
            u = u-1
            v = v-1
            if languages[u] & languages[v]: continue
            dontspeak.add(u)
            dontspeak.add(v)

1734. Decode XORed Permutation

leetcode.com/problems/decode-xored-permutation/

Medium

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

처음 n 개의 양의 정수의 순열 인 정수 배열 perm이 있습니다. 여기서 n은 항상 홀수입니다.
이는 인코딩 된 [i] = perm [i] XOR perm [i + 1]과 같이 길이 n-1로 인코딩 된 다른 정수 배열로 인코딩되었습니다. 예를 들어 perm = [1,3,2]이면 인코딩 = [2,1]입니다.
인코딩 된 배열이 주어지면 원래 배열 perm을 반환합니다. 답변이 존재하고 고유하다는 것이 보장됩니다.

Example 1:

Input: encoded = [3,1] Output: [1,2,3] Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:

Input: encoded = [6,5,4,6] Output: [2,4,1,5,3]

Constraints:

3 <= n < 105
n is odd.
encoded.length == n - 1

Compute the XOR of the numbers between 1 and n, and think about how it can be used. Let it be x.

Show Hint 2

Think why n is odd.

Show Hint 3

perm[0] = x XOR encoded[1] XOR encoded[3] XOR encoded[5] ...

Hide Hint 4

perm[i] = perm[i-1] XOR encoded[i-1]

* note

encoded[i] = perm[i] XOR perm[i + 1]

e[0] = p[0] ^ p[1] -> p[0] = e[0] ^ p[1]

e[1] = p[1] ^ p[2] -> p[1] = e[1] ^ p[2]

e[2] = p[2] ^ p[3] -> p[2] = e[2] ^ p[3]

e[3] = p[3] ^ p[4]

e[4] = p[4] ^ p[5] -> p[4] = e[4] ^ p[5]

e[5] = p[5] ^ p[6] -> p[5] = e[5] ^ p[6]

디코드 문제는 처음에는 당황스럽지만, 몇개를 해보면 익숙해진다. 연습만이 해답이다.

class Solution:
    def decode(self, encoded: List[int]) -> List[int]:        
        xor_all_elements, xor_except_last_element = 0, 0
        
        for val in range(1, len(encoded)+2):
            xor_all_elements ^= val
            
        for i, val in enumerate(encoded):
            if i % 2: continue
            xor_except_last_element ^= val
        
        # xor_all_elements ^ xor_except_last_element = the last element of the original array
        ans = [xor_all_elements ^ xor_except_last_element]

        for val in encoded[::-1]:
            ans.append(ans[-1] ^ val)
            
        return ans[::-1]

1735. Count Ways to Make Array With Product

leetcode.com/problems/count-ways-to-make-array-with-product/

Hard

32Add to ListShare

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [ni, ki], find the number of different ways you can place positive integers into an array of size ni such that the product of the integers is ki. As the number of ways may be too large, the answer to the ith query is the number of ways modulo 109 + 7.

Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the ith query.

Example 1:

Input: queries = [[2,6],[5,1],[73,660]] Output: [4,1,50734910] Explanation: Each query is independent. [2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1]. [5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1]. [73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 109 + 7 = 50734910.

Example 2:

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]] Output: [1,2,3,10,5]

Constraints:

1 <= queries.length <= 104
1 <= ni, ki <= 104

Prime-factorize ki and count how many ways you can distribute the primes among the ni positions.

Hide Hint 2

After prime factorizing ki, suppose there are x amount of prime factor. There are (x + n - 1) choose (n - 1) ways to distribute the x prime factors into k positions, allowing repetitions.