Hex.*

LC - Weekly Contest 302

Posted on In
Ranking: 3200/7092; Completed Questions: 3/4; Mark: 12/18

2341. Maximum Number of Pairs in Array

  • Store the nums value as the key, the frequency of each num as value
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# O(n) time | O(n) space
class Solution:
    def numberOfPairs(self, nums: List[int]) -> List[int]:
        h = {}
        for num in nums:
            if num not in h:
                h[num] = 1
            else:
                h[num] +=1

        cnt0 = 0
        cnt1 = 0
        for k, v in h.items():
            temp0, temp1 = divmod(v, 2)
            cnt0+= temp0
            cnt1+= temp1
        return [cnt0, cnt1]

2342. Max Sum of a Pair With Equal Sum of Digits

  • Store the sum of each digit in each num as the key, and store the values of the corresponding nums as the value
  • make the value sorted
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# O(n) time | O(n) space
from sortedcontainers import SortedList

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        h = {}
        for num in nums:
            s = 0
            temp = num
            while temp:
                s += temp % 10
                temp//=10

            if s not in h:
                h[s] = SortedList([num])
            else:
                h[s].add(num)

        maxi = -1
        for k, v in h.items():
            if len(v) <2:
                continue
            maxi = max(maxi, v[-1]+v[-2])
        return maxi

2343. Query Kth Smallest Trimmed Number

  • Trim the string based on the trim
  • store the index and result into arr
  • sort arr
  • get the kth smallest trimmed number
1
2
3
4
5
6
7
8
9
10
11
# O(nm) time | O(n) space
class Solution:
    def smallestTrimmedNumbers(self, nums: List[str], queries: List[List[int]]) -> List[int]:
        ans=[]
        for k,trim in queries:
            arr=[]
            for i,v in enumerate(nums):
                arr.append((v[-trim:],i))
            arr.sort()
            ans.append(arr[k-1][1])
        return ans

2344. Minimum Deletions to Make Array Divisible

  • use math.gcd to get the greatest common divisor of the list
  • sort the numbers list
  • travers numbers list and when the common divisor can divides the current number without a reminder, which means the current index is the number of deleted times
1
2
3
4
5
6
7
8
9
10
11
12
# O(nlogn) time | O(1) space
class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        cur = numsDivide[0]
        for i in numsDivide[1:]:
            cur = math.gcd(cur, i)

        nums.sort()
        for i, v in enumerate(nums):
            if cur%v == 0:
                return i
        return -1

Note

The math.gcd() method returns the greatest common divisor of the two integers int1 and int2.

GCD is the largest common divisor that divides the numbers without a remainder.

GCD is also known as the highest common factor (HCF).

Tip: gcd(0,0) returns 0.

1
2
3
math.gcd(int1, int2)

# return An int value, representing the greatest common divisor (GCD) for two integers