🥂成雙成對 Check If Array Pairs Are Divisible by k_LC #1497

Karsten Winegeart on Unsplash

題目敘述 Check If Array Pairs Are Divisible by k

給定一個長度為偶數的整數陣列arr，和一個整數k 。

我們想把陣列元素兩兩一組組成pair，使得每個pair的總和可以被k整除。

如果做得到，返回True。

如果不行，返回False。

測試範例

Example 1:

Input: arr = [1,2,3,4,5,10,6,7,8,9], k = 5
Output: true
Explanation: Pairs are (1,9),(2,8),(3,7),(4,6) and (5,10).

Example 2:

Input: arr = [1,2,3,4,5,6], k = 7
Output: true
Explanation: Pairs are (1,6),(2,5) and(3,4).

Example 3:

Input: arr = [1,2,3,4,5,6], k = 10
Output: false
Explanation: You can try all possible pairs to see that there is no way to divide arr into 3 pairs each with sum divisible by 10.

約束條件

Constraints:

• arr.length == n

arr陣列長度= n

• 1 <= n <= 10^5

n 介於1~十萬之間。

• n is even.

陣列長度n是偶數

• -10^9 <= arr[i] <= 10^9

每個陣列元素介於 負十億~正十億之間

• 1 <= k <= 10^5

k值介於1~十萬之間。

演算法 餘數配對

從餘數去做配對

餘1 的和 餘k-1的去配對

餘2 的和 餘k-2的去配對

依此類推...

假如彼此的出現次數不相等，代表無法完美配對，直接返回False。

接著，有兩個Special Case要特別處理。

餘k//2 的和 餘k//2的去配對，所以pair數只有一半而已。

餘0 的和 餘0的去配對，所以pair數也只有一半而已。

如果最後pair總數 = n // 2 = 陣列長度 // 2，

代表我們可以把陣列元素兩兩一組組成pair，使得每個pair的總和可以被k整除。

做得到，返回True。

否則，返回False。

程式碼 餘數配對

class Solution:
    def canArrange(self, arr: List[int], k: int) -> bool:
        
        # Length of array
        n = len(arr)

        # key: remainder of mod k
        # value: total counting of number with respect to mod k
        count = [0 for _ in range(k) ]
        for num in arr:
            count[num%k] +=1        
        
        # Try to make pair with 1 mod k and k-1 mod k
        #                       2 mod k and k-2 mod k
        #                       and so on...
        
        i,j =1,k-1
        pairs  = 0
        while i<j :

            # Number of i mod k =/= Number of j mod k
            # We cannot make exactly n / 2 pairs
            if count[i]!=count[j]:
                return False
            pairs += count[i]
            i+=1
            j-=1

        # Try to make pair with k/2 mod k and k/2 mod k
        if  i==j:
            pairs+=count[i]//2
        
        # Try to make pair with 0 mod k and 0 mod k
        pairs+= count[0]//2
       
        return pairs == n//2

複雜度分析

時間複雜度: O(n)

掃描每個數字一次，建立count表格，紀錄mod k 對應的餘數出現次數。

空間複雜度: O(k)

count表格紀錄從餘0~餘k-1的出現次數，表格大小為O(k)

Reference

[1] Check If Array Pairs Are Divisible by k - LeetCode