Problem Explanation

Given an array and a target sum (k), the task is to check if it is possible to divide the array into pairs such that the sum of elements in each pair is divisible by k.

Approach

The approach used to solve this problem is by using a bucket or counting sort. In this case, a vector bucket of size k is first created. All numbers are reduced modulo k and their counts are tracked in the bucket.

Let's take an example: arr = [1, 2, 3, 4, 5, 10, 6, 7, 8, 9], k = 5. If we take modulo of each number with respect to k, this gives us indices into buckets: 1, 2, 3, 4, 0, 0, 1, 2, 3, 4. Now we want pairs which add up to k, so we need pairs that add up to the same indices: (1, 4), (2, 3), (0, 0). The numbers at index 0 are special because they are already divisible by k, so they need to form pairs among themselves, hence their count must be even. Next, the count of numbers at indices i and k-i also needs to match otherwise we wouldn't be able to pair them up to form a sum divisible by k.

If at the end of checking each bucket, the conditions still hold, then it is possible to divide the array into pairs, else not.

Solution

Python

1
2python
3class Solution:
4    def canArrange(self, arr: List[int], k: int) -> bool:
5        bucket = [0]*k
6
7        for a in arr:
8            i = a % k
9            if i < 0:
10                i += k
11            bucket[i] += 1
12
13        for i in range(k):
14            if i == 0:
15                if bucket[i] % 2 != 0:
16                    return False
17            elif (bucket[i] + bucket[k - i]) % 2 != 0:
18                return False
19
20        return True

Java

1
2java
3class Solution {
4    public boolean canArrange(int[] arr, int k) {
5        int[] bucket = new int[k];
6
7        for(int a : arr) {
8            int i = ((a % k) + k) % k;
9            bucket[i]++;
10        }
11
12        if(bucket[0] % 2 != 0)
13            return false;
14        for(int i = 1; i <= k / 2; i++)
15            if(bucket[i] != bucket[k - i])
16                return false;
17        return true;
18    }
19}

JavaScript

1
2javascript
3var canArrange = function(arr, k) {
4    let bucket = new Array(k).fill(0);
5
6    for(let a of arr) {
7        let i = ((a % k) + k) % k;
8        bucket[i]++;
9    }
10
11    if(bucket[0] % 2 != 0)
12        return false;
13    for(let i = 1; i <= Math.floor(k / 2); i++)
14        if(bucket[i] != bucket[k - i])
15            return false;
16    return true;
17};

C++

1
2cpp
3class Solution {
4 public:
5  bool canArrange(vector<int>& arr, int k) {
6    vector<int> bucket(k);
7
8    for (const int a : arr) {
9      int i = a % k;
10      if (i < 0)
11        i += k;
12      ++bucket[i];
13    }
14
15    for (int i = 0; i < k; ++i)
16      if (i == 0) {
17        if (bucket[i] % 2 != 0)
18          return false;
19      } else if ((bucket[i] + bucket[k - i]) % 2 != 0) {
20        return false;
21      }
22
23    return true;
24  }
25};

C#

1
2csharp
3public class Solution {
4    public bool CanArrange(int[] arr, int k) {
5        int[] bucket = new int[k];
6
7        for(int j = 0; j < arr.Length; j++) {
8            int i = ((arr[j] % k) + k) % k;
9            bucket[i]++;
10        }
11
12        if(bucket[0] % 2 != 0)
13            return false;
14        for(int i = 1; i <= bucket.Length / 2; i++)
15            if(bucket[i] != bucket[k - i])
16                return false;
17        return true;
18    }
19}

This approach works very efficiently by creating a lookup table storing frequencies of numbers modulo k. The most important checks are to ensure that numbers at index 0 in the bucket have even frequencies as they are already divisible by k. In addition, it's also important to check that numbers at indices i and k-i have the same frequencies to ensure they can be paired and their sum divided by k.

This solution is elegant, and its time complexity is O(n), making it optimal for large data inputs. The code can be easily understood, implemented and tested in various programming languages.

Finding the right way to solve problems by using programming is very challenging. It involves a strong understanding of programming basics, data structures and algorithms. But, by working on such problems, it strengthens one’s problem-solving ability and also enhances programming skills.

If you're just getting started on your coding journey or even have some experience, problem-solving skills and hands on coding will definitely boost your confidence. So keep learning new concepts everyday and apply them to your coding.

And lastly remember, "The separation of talent and skill is one of the greatest misunderstood concepts for people who are trying to excel, who have dreams, who want to do things. Talent you have naturally. Skill is only developed by hours and hours and hours of beating on your craft." - Will Smith.