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.
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Algorithms
  3. Implementation
  4. Divisible Sum Pairs
  5. Discussions

Divisible Sum Pairs

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 1384 Discussions, By:

votes

Please Login in order to post a comment

  • usinha02 5 years ago+ 0 comments

    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;
    }
    
    285|
    Permalink
  • 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 ;)

    33|
    Permalink
  • 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
    
    25|
    Permalink
  • 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 ((

    18|
    Permalink
  • 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
    
    15|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature