I did this in O(n)

If any suggestions please let me know

using namespace std;
int main(){
   
   int n;
   int k;
   cin >> n >> k;
   int a[n];
   int m[k];
   for(int i=0; i<k; i++)
       m[i]=0;
    for(int i = 0; i < n; i++){
       cin >> a[i];
        m[a[i]%k]++;
    }
    int sum=0;
    sum+=(m[0]*(m[0]-1))/2;
     for(int i=1; i<=k/2 && i!=k-i; i++){
         sum+=m[i]*m[k-i];
     }
    if(k%2==0)
        sum+=(m[k/2]*(m[k/2]-1))/2;
    cout<<sum;
    return 0;
}

WolfEng 5 years ago+ 0 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 ;)

RodneyShag 4 years ago+ 0 comments

Simple and efficient O(n+k) solution

From my HackerRank solutions which contains additional comments in code.

Runtime: O(n + k), by doing only 1 pass of the values
Space Complexity: O(k)

We keep track of the mod values in buckets for each number we read. We can do this by creating k buckets where bucket i counts each number n where n % k = i.

Notice that each bucket has a corresponding complement bucket. That is, if we take the mod value of one bucket and add it to the mod value of another bucket, we get k.

Bucket   Complement Bucket
------   -----------------
   0           0
   1          k-1
   2          k-2
   3          k-3
      ......
  k-3          3
  k-2          2
  k-1          1

As we come across each number, we find its corresponding complement bucket. Each number in this complement bucket can be paired with our original number to create a sum divisible by k

static int divisibleSumPairs(int n, int k, int[] ar) {
    int [] bucket = new int[k];
    int count = 0;
    for (int value : ar) {
        int modValue = value % k;
        count += bucket[(k - modValue) % k]; // adds # of elements in complement bucket
        bucket[modValue]++;                  // saves in bucket
    }
    return count;
}

Sample Bucket placement

For the following sample input

6 3
1 3 2 6 1 2

We have

Bucket   Integers    Count
------   --------    -----
  0        3, 6        2
  1        1, 1        2
  2        2, 2        2

neldarov 3 years ago+ 0 comments

The main trouble with hackerrank problems is the way the problem is explained, poorly explained. It takes half an hour to get what it requires but 5 mins to code ((

rahulrajpl 3 years ago+ 0 comments

For Python Lovers

def divisibleSumPairs(n, k, ar):
    # Complete this function
    count = 0
    for i in range(n-1):
        j = i+1
        while j < n:
            if ((ar[i] + ar[j]) % k) == 0:
                count += 1
            j += 1
    return count

Load more conversations