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

  • WolfEng
     + 10 comments

    For those wondering about a Java solution. The workings are pretty much the same as has been posted before in regards to an O(n) solution:

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        int a[] = new int[k];
        int count = 0;
        for(int a_i=0; a_i < n; a_i++){
            int number = in.nextInt();
            number = number % k;
            int complement = number == 0 ? k : number;
            count += a[k-complement];
            a[number] += 1;
        }
        System.out.println(count);
    }

    Basically fetches the complement in the corresponding bucket adding to the result whatever is stored there. Then adds 1 to the bucket that corresponds to the remainder of the input.

    Taking the provided example:

    6 3
1 3 2 6 1 2

Input: 1
INITIAL STATE: Bucket[0]:0; Bucket[1]:0; Bucket[2]:0 Count:0
Remainder r: 1
Complement: 3 - r = 2
count+= Bucket[2]:0
bucket[1]++

Input: 3
INITIAL STATE: Bucket[0]:0; Bucket[1]:1; Bucket[2]:0 Count:0
Remainder r: 0
Complement: 3 - r = 3 -> 0 //(3 gets switched for 0 =) ).
count+= bucket[0]:0
bucket[0]++

Input: 2
INITIAL STATE: Bucket[0]:1; Bucket[1]:1; Bucket[2]:0 Count:0
Remainder r: 2
Complement: 3 - r = 1
count+= bucket[1]:1
bucket[2]++

Input: 6
INITIAL STATE: Bucket[0]:1; Bucket[1]:1; Bucket[2]:1 Count:1
Remainder r: 0
Complement: 3 - r = 3 -> 0
count+= bucket[0]:1
bucket[0]++

Input: 1
INITIAL STATE: Bucket[0]:2; Bucket[1]:1; Bucket[2]:1 Count:2
Remainder r: 1
Complement: 3 - r = 2
count+= bucket[2]:1
bucket[1]++

Input: 2
INITIAL STATE: Bucket[0]:2; Bucket[1]:2; Bucket[2]:1 Count:3
Remainder r: 2
Complement: 3 - r = 1
count+= bucket[1]:2
bucket[2]++

FINAL STATE: Bucket[0]:2; Bucket[1]:2; Bucket[2]:2 Count:5

    Hopefully I made no mistakes in the example run ;)