1497. Check If Array Pairs Are Divisible by k

Time: O(n)

Space: O(k)

Intuition

If we can arrange pairs summing to k, every element must have a partner. For each element x: need element k-x. Count frequencies and check.

Algorithm

1If n is odd: return false.
2Count frequencies. For each value v: if v+v==k, need even count. Else freq[v] must equal freq[k-v].

Common Pitfalls

•Handle k/2 case specially (needs even frequency). Also handle 0: need even count if 2*0==k.

1497.cs

// Approach: Frequency of remainders mod k; remainder r must pair with remainder k-r; remainder 0 must be even-count.
// Time: O(n) Space: O(k)

public class Solution
{
    public bool CanArrange(int[] arr, int k)
    {
        int[] count = new int[k];

        for (int i = 0; i < arr.Length; i++)
        {
            arr[i] %= k;
            count[arr[i] < 0 ? arr[i] + k : arr[i]]++;
        }

        if (count[0] % 2 != 0)
            return false;

        for (int i = 1; i <= k / 2; i++)
        {
            if (count[i] != count[k - i])
                return false;
        }

        return true;
    }
}

Was this solution helpful?