We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Divisible Sum Pairs
  5. Discussions

Divisible Sum Pairs

  • delight182
     + 7 comments

    My O(n) C# solution:

    static void Main(String[] args)
{
    var nk = Console.ReadLine().Split(' ').Select(Int32.Parse)
                    .ToArray();
    int n = nk[0];
    int k = nk[1];
    var arr = Console.ReadLine().Split(' ').Select(Int32.Parse)
                     .ToArray();
        
    var count = 0;
    var counts = new int[k];
    for (var i = 0; i < n; i++)
    {
        // the idea is that if (a1 + a2) % k == 0
        // then (a1 % k + a2 % k) should be equal to k (or 0)
        var bucket = arr[i] % k;
        // adding all new combinations with arr[i] to the count
        // also handling bucket == 0 with % k here
        count += counts[(k - bucket) % k];
        counts[bucket]++;
    }
        
    Console.WriteLine(count);
}