Loading...

Sort 429 Discussions, By:

  • usinha02 + 24 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;
    }
    
    • Noroi + 2 comments

      Can you please explain the logic here of how did you deduce the total number of pairs modding to k?

      • P
        petreeftime + 13 comments

        The idea is that you separate elements into buckets depending on their mod k. For example, you have the elements: 1 3 2 6 4 5 9 and k = 3

        mod 3 == 0 : 3 6 9
        mod 3 == 1 : 1 4
        mod 3 == 2 : 2 5
        

        Now, you can make pairs like so: Elements with mod 3 == 0 will match with elements with (3 - 0) mod k = 0, so other elements in the mod 3 == 0 list, like so:

        (3, 6) (3, 9) (6, 9)
        

        There will be n * (n - 1) / 2 such pairs, where n is length of the list, because the list is the same and i != j. Elements with mod 3 == 1 will match with elements with (3 - 1) mod k = 2, so elements in the mod 3 == 2 list, like so:

        (1, 2) (1, 5) (4, 2) (4, 5)
        

        There will be n * k such elements, where n is the length of the first list, and k of the second.

        Because you don't need to print the actual pairs, you need to store only the number of elements in each list.

        • Noroi + 1 comment

          Thanks this lays it down pretty good. This should be in the editorial.

          • DB
            danjb + 2 comments

            It is an optimal solution, but keep in mind: Reading the input sizes is really important in a competition. Here we have N <= 100 and it would be a waste of time to implement the optimal solution. For N <= 10^9 however, this optimal solution would be better.

            • BG
              bgenchel + 1 comment

              if the processing is trivial on the inputs, as in the case of processing the mod counts, why should input size matter?

              • DB
                danjb + 0 comments

                Small input size: You don't have to think that hard and you can implementend a simpler solution, which needs less time to write the code for and debug.

            • P
              petreeftime + 1 comment

              Yes, but this second solution is a better learning tool for modular arithmetics. The other solution is trivial.

              • AA
                aarohiagarwal12 + 1 comment

                Don't you think this might increase the space complexity if k>10 or something..??

                • lovereli + 0 comments

                  There is always a tradeoff between space and time complexity. Otherwise we might be in a better world!!

        • NJ
          Jyothi_sirigi + 1 comment

          But in the problem it is given as we have to print the number of (i,j) pairs and the given condition is i

          • KN
            Khoa190602 + 0 comments

            It said to print the number of pairs not the pairs themselves

        • kiamottullah + 0 comments

          hey please tell me that which algorithom or any other books are u flowing >?

        • PK
          prakashk885 + 0 comments
          [deleted]
        • JT
          Jlookup + 7 comments

          Thanks @usinha02 for the algo, and @petreeftime for the explanation. Here's an implementation in Python. Some bits are a little clunky. Feedback Please.

          Python 3:

          import sys
          
          
          n,k = [int(x) for x in input().strip().split(' ')]
          a = [int(a_temp) for a_temp in input().strip().split(' ')]
          
          mods = [0] * k
          for i in range(n):
              mods[a[i] % k] += 1 
          
          count = 0
          for i in range(int(k/2) + 1):
              if i == 0:
                  count += int(mods[0] * (mods[0] - 1) / 2)
              elif float(i) == (k/2):
                  count += int(mods[int(k/2)] * (mods[int(k/2)] - 1) / 2)
              else:
                  count += int(mods[i] * mods[k-i])
          
          print (count)
          
          • SebastianNielsen + 6 comments

            What time complexity is that? Is it better than mine?

            n,k = (int(x) for x in input().split())
            lst = list(map(int, input().split()))
            
            count = 0
            for i in range(len(lst)-1):
                for x in range(1+i, len(lst)):     
                    if (lst[i] + lst[x]) % k == 0:
                        count += 1
                    
            print(count)
            
            • emptyset + 0 comments
              [deleted]
            • surajt_oneliner + 0 comments

              fab man :)

            • LeHarkunwar + 5 comments

              How about this in python ?

              def divisibleSumPairs(n, k, ar):
                  return sum(1 for i in range(n) for j in range(n) if i < j and (ar[i]+ar[j])%k == 0)
              
              • SG
                ghosh_saikat4000 + 0 comments

                It's quadratic ... Less lines of code doesn't necessarily mean less time complexity.

              • MA
                malexand314 + 0 comments

                It's the exact same solution as above from SebastianNielsen, just in a one-line format.

              • RT
                Ravitejacms + 0 comments

                Awesome!!

              • washinpi + 0 comments

                i think this code will take less runtime than yours :)

                def divisibleSumPairs(n, k, ar):
                    # Complete this function
                     return sum(1 for i in range(n) for j in range(i+1 ,n) if (ar[i]+ar[j])%k == 0)
                
              • jaymzdee + 0 comments

                Use combinations...

                def divisibleSumPairs(n, k, ar):
                    # Complete this function  
                    return len([x for x in combinations(range(n), 2) if (ar[x[0]]+ar[x[1]])%k==0])
                
            • skanth004 + 2 comments

              I did the same logic in java :)

              for(int i=0; i<n; i++){
                      for(int j=1;j<n;j++){
                          if (i < j){
                          a = ar[i] + ar[j];
                          if (a % k == 0){
                              count++;
                          }}
                      }
                  }
              
              • skanth004 + 0 comments
                [deleted]
              • LR
                LukeRocheDev + 1 comment

                works but is hard to read... i would do

                for(int i=0; i<n-1; i++){
                        for(int j=i+1;j<n;j++){
                            a = ar[i] + ar[j];
                            if (a % k == 0)
                                count++;
                            
                        }
                    }
                
                • KH
                  bytes_and_bits + 3 comments

                  It does not pass all test cases

                  • C
                    correia_mario + 1 comment
                    [deleted]
                  • C
                    correia_mario + 0 comments

                    work to me

                    count=0;
                    for(i=0;i<(ar.length)-1;i++)
                        for(j=i+1;j<(ar.length);j++)
                            if((ar[i]+ar[j])%k==0)
                                count++;
                    return count;
                    
                  • sanchitgnawali + 0 comments

                    make sure you use

                    a = ar[i] + ar[j]
                    

                    my solution was similar but didn't pass the all the test cases because i was using

                    a = i+j
                    
            • baduker + 1 comment

              Why are we substracting 1 from the array length in the first loop?

              • juri_the_eagle + 0 comments

                Cause the second number has to be at a later position, there's never a pair for the last position.

            • chinmay43 + 0 comments

              How about this? Here is my Python 3 code: I used combinations

              def divisibleSumPairs(n, k, ar):
                  sum_lst = list()
                  res = list()
                  comb_list = (list(combinations(ar, 2)))
                  for i in comb_list:
                      sum_lst.append(i[0] + i[1])
                  for i in sum_lst:
                      if (i % k) == 0:
                          res.append(i)
                  return (len(res))
              
          • oliver_hare + 5 comments

            Slightly simpler O(n) python3 code

            def divisibleSumPairs(n, k, ar):
                nums = [0] * k
                count = 0
                for ele in ar:
                    modu = ele % k
                    count += nums[(k - modu) % k]
                    nums[modu] += 1
                return count
            
            • XR
              Token_404 + 0 comments
              [deleted]
            • SZ
              toosengzhao + 1 comment

              Could you provide some explanations to this? Appreciate it lots!

              • djaychela + 1 comment

                I've just spent half an hour looking through this and the parent comments above (which are given some credit for the idea) - it's a really clever solution to the problem, and if you read petreeftime's description above, it covers it pretty well. I found a key to understanding it was to alter the code so that you see the contents of all the relevant variables at each step, and then it became clear how it was working (I'm using Python 3.6, hence the f strings):

                def divisibleSumPairs(n, k, ar):
                    nums = [0] * k
                    count = 0
                    for ele in ar:
                        modu = ele % k
                        print(f"{ele} {modu} {count} {nums} - after modu")
                        count += nums[(k - modu) % k]
                        print(f"{ele} {modu} {count} {nums} - after count+=")
                        nums[modu] += 1
                        print(f"{ele} {modu} {count} {nums} - after nums+=")
                        print("-----------------------")
                    return count
                

                The first step works out the mod value of the current array element - that's really the only thing that matters - a 3 and a 6 will have the same effect as a 3 and a 3 (for a k of 3).

                Next step is to increment the counter by the number of possible combinations that yield k mod 0.

                The third step adds the current array element to the nums list, which will allow that to be counted towards future possibilities in other steps.

                • FK
                  felix_jatmiko + 0 comments

                  The second step exists because ((k - modu % k) + (modu % k)) % k == 0.

            • NP
              nivedpk1994 + 0 comments

              brilliant logic

            • djaychela + 0 comments

              Great - just spent half an hour trying to work out how this worked, and now I have I feel like I've achieved something today! Thanks for the code.

            • trgiangvp3 + 0 comments

              God

          • AE
            amaals_emam + 1 comment

            count += int(mods[0] * (mods[0] - 1) / 2) from where did this equation come up?

            • PK
              rajusujan2020 + 0 comments

              because n*n-1/2 pairs are available

          • AA
            aarohiagarwal12 + 0 comments

            Can you please explain, why is this part used?

            elif float(i) == (k/2): count += int(mods[int(k/2)] * (mods[int(k/2)] - 1) / 2)

          • DT
            dtyagi1 + 0 comments

            print sum(1 for i in itertools.combinations(ar,2) if sum(i)%k==0)

          • DG
            Dimple151997 + 0 comments

            can u explain the code

          • RR
            rahulrajpl + 0 comments

            Why is this so complex? 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

        • A
          smdaziz + 0 comments

          Thanks for the explanation petreeftime! How does it take care of choosing only those pairs whose index i < j?

        • tanzeelosama + 0 comments

          GENIOUS!

        • vikki_kumar + 0 comments

          Thanks this is really helpfull.

        • VS
          ShikamaruNara + 0 comments

          But what happens when mod 3=0 elemtns are all {3,3,3} There would be no pairs in bw them , but as per your solution , we would get 3 again ??

        • SS
          sri_sam229 + 0 comments

          good logic but i am interested to know if that helped any complexity.

        • ShivendraKadam + 0 comments

          Nice explaination Thank You

        • PK
          kharatpriyank + 0 comments

          Thank you usinha02 for the elegant solution, and thank you petreeftime for an awesome explanation! Although I understood most of it, and this maybe most naive doubt that I have. I wasn't able to understand the following condition:

          if(k%2==0)
                  sum+=(m[k/2]*(m[k/2]-1))/2;
          

          Thanks in advance.

        • asiyer + 0 comments

          When you say, n is the length of the first list, and k the length of the second, do you mean the list of mod3 == x ?or the input list?

      • GC
        ghcho20 + 0 comments
        [deleted]
    • delight182 + 0 comments

      Isn't it O(n + k) (or O(max(n, k)))? You actually don't need to iterate over m, see my O(n) solution.

      Also, I didn't run your code but your result looks off by m[k/2]*m[k/2-1] because your termination condition is i<=k/2 (should be i<k/2 as you handle this case separately).

      Otherwise you got the idea right, good job!

    • wkusnierczyk + 0 comments

      This is O(n + k), not O(n).

      In particular, when n = 0 you have:

      -- O(k) space allocation (m[k])
      -- O(k) run time (for(int i=1; i<=k/2 && i!=k-i; i++) loop).

    • MisterHax + 1 comment

      For anyone that wishes for a little more background like I did on this stuff, I found the explanations of modular arithmetic on Khan Academy really helpful.

      for(int i = 0; i < n; i++){
          cin >> a[i];
          m[a[i]%k]++;
      }
      

      This above piece of code is just finding the amount of elements in each "equivalence class" and all code after that is taking advantage of the addition property of modular arithmetic:

      (A+B) mod C = ((A mod C) + (B mod C)) mod C
      

      Hope this helps out there! Great solution!

      • D
        de_ganxta + 0 comments

        thanks

    • GC
      ghcho20 + 1 comment

      I have a question.

      for (int i=1; i<=k/2 && i!=k; i++)
          sum += m[i]*m[k-i];
      

      Here, m[i] seems not to have information about the order.
      Does it meet the constraint of i<j ?
      Looks like it does not tell (1,5) and (5,1).

      • P
        petreeftime + 1 comment

        In this case i is at most k/2 = 2 and k - i is at least k - k/2 = 3, you can only have (1, 5). This is also true for any other example.

        • GC
          ghcho20 + 1 comment

          I'm afraid I don't get it right.
          Let me rephrase the question.
          For k=6, if you have input '1, 5, ... , 5, 1'
          Both first & second '1' enters m[1] slot
          Likewise both '5' to m[5] slot
          m[i]*m[k-i] count both anyhow (for i <= k/2)
          But (5,1) must not count because of i<j constraint.
          Am I missing something ?
          thanks

          • HC
            antipyrrhus + 0 comments

            No. For your example with k=6, if the input were [a0,a1,a2,a3] = [1,5,5,1], then both of the (5,1) (that is, (a1,a3) and (a2,a3)) count because in both cases i < j. (1 < 3 and 2 < 3)

    • irshad_ck + 6 comments

      You can use this logic to reduce the code. {

      int count

      for(int i = 0 ; i <= n; i++){

          for(int j = 0; j < n; j++ ){
      
              if(i < j){
      
                  if((a[i]+a[j])%k == 0){
                      count++; 
      
                  }
              }
          }
      }
      

      }

      • marigabibenitez + 0 comments
        [deleted]
      • tourofer + 0 comments
        [deleted]
      • abhilashpani651 + 0 comments

        it displays floating point exception

      • jay209 + 0 comments

        It has O(n^2) complexity!

      • PS
        prabhjot8126 + 4 comments

        you could have done like this could reduce little more

        for(int i=0;i<n;i++)
                {
                for(int j=i+1;j<n;j++)
                    {
                        if((a[i]+a[j])%k==0)
                            {
                            count++;
                        }
                }
            }
        
        • HL
          hira89 + 3 comments

          I came up with same logic, but for input 6 3 1 3 2 6 1 2 my answer is 10 instead of 5.. i think its counting reverse combination too. ex: 0,3 and 3,0 if its divisible by k.

          • PS
            prabhjot8126 + 3 comments

            @hirababu089 there is no possible way for which it could make a pair such as (3,0) becouse in the second loop the smallest value possible is i+1 (the inital j position) anyways here the entire code may be you are doing some silly mistake like putting j=1 instead of j=i+1; in second loop

            #include <math.h>
            #include <stdio.h>
            #include <string.h>
            #include <stdlib.h>
            #include <assert.h>
            #include <limits.h>
            #include <stdbool.h>
            
            int main() {
                int n; 
                int k; 
                int count=0;
                scanf("%d %d", &n, &k);
                int *a = malloc(sizeof(int) * n);
                for(int a_i = 0; a_i < n; a_i++){
                   scanf("%d",&a[a_i]);
                }
                for(int i=0;i<n;i++)
                    {
                    for(int j=i+1;j<n;j++)
                        {
                            if((a[i]+a[j])%k==0)
                                {
                                count++;
                            }
                    }
                }
                printf("%d",count);
                
                // write your code here
                return 0;
            }
            
            • sinha_amrit093 + 1 comment

              Instead of using two loops why not just use one? Like mine:

              for(int i=0;i<n;i++)
                      {
                      val=a[i]+a[i+1];
                      if(val%k!=0)
                          {
                          count++;
                      }
              }
              
              • DP
                dinesh_pi + 0 comments

                these can only find consecutive pairs

            • PK
              prasanna_STR + 0 comments

              I  thinks its wrong

            • anshumanc007 + 0 comments

              see instesd of writing j=i+1; we add a condition if(A[i]>A[j]);then sum=A[i]+A[j] else sum=1 then if sum%k==0 c=c+1 it will not work?????

          • satyambhalla17 + 0 comments

            Also check for the condition where i < j then increment the count variable.

          • JS
            jyoshu + 0 comments
            [deleted]
        • mikepare93 + 0 comments

          I did something similar and passed. I'm pretty sure this type of solution is O(nlogn).

        • VA
          varun_1995 + 0 comments

          run outer loop for i < n - 1

        • LS
          logasanjayr5055 + 0 comments

          this will eliminate the comparison of certain numbers

      • anicse0904071 + 0 comments

        the first loop doesnt need to loop through i<=n , it should loop through i< n-1, because i should always be less than j .

    • marigabibenitez + 0 comments
      [deleted]
    • erichamion + 1 comment

      A similar idea in C#. A bit more verbose, but I think the logic is a bit clearer. It also avoids repeating the "n * (n - 1) / 2" formula twice.

      public static void Main(string[] args)
      {
      	// First input line contains n and k. Ignore n because it will be
      	// implied by the second input line.
      	int k = int.Parse(Console.ReadLine().Split(' ')[1]);
      
      	// When reading the line, we only care about each value mod k.
      	// Read the line in, and convert it to a dictionary/map with
      	// value-mod-k as key, and the number of times that value-mod-k
      	// occurs as the value.
      	var modCounts = Console.ReadLine()
      		.Split(' ')
      		.Select(x => int.Parse(x) % k).GroupBy(x => x)
      		.ToDictionary(x => x.Key, x => x.Count());
      
      	// Initialize the result
      	int result = 0;
      
      	// We only need to check the first k/2 keys (plus the middle key
      	// if k is odd), because the other keys are "complementary" (may
      	// not be the correct term, see comment below) to the ones we check.
      	for (int modValue = 0; 2 * modValue <= k; modValue++)
      	{
      		int modCount;
      
      		// If modCounts does not contain the key modValue, then modCount will
      		// be 0.
      		modCounts.TryGetValue(modValue, out modCount);
      
      		// "Complement" may not be the correct term for this. As I'm using it,
      		// complement(n) with respect to k is defined as the value c
      		// such that (n + c) % k == 0 and c % k == 0.
      		var complementValue = (k - modValue) % k;
      		if (modValue == complementValue)
      		{
      			// If modValue == complementValue (which happens if modValue == 0,
      			// or if modValue == (k + 1) / 2 and k is odd), then each occurrence
      			// of modValue pairs with other occurrences of the same modValue.
      			// The number of pairs within modCount identical values is
      			// Sum (from i=1 to modCount-1) of i.
      			// Sum (from i=1 to n) of n is ((n * (n + 1)) / 2), which is equivalent to
      			// (n^2 + n) / 2. With n = modCount - 1:
      			// ((modCount - 1)^2 + (modCount - 1) / 2
      			// ((modCount^2 - 2 * modCount + 1) + (modCount - 1)) / 2
      			// (modCount^2 - modCount) / 2
      			result += modCount * (modCount - 1) / 2;
      		}
      		else
      		{
      			// In the normal case, modValue != complementValue, we just have
      			// modCount * complementCount pairs.
      			int complementCount;
      			modCounts.TryGetValue(complementValue, out complementCount);
      			result += modCount * complementCount;
      		}
      	}
      
      	Console.WriteLine(result);
      }
      
      • BK
        burak54 + 0 comments

        My eyes bleed. Too much comment lines.

    • MB
      bozhko_maksim_s1 + 4 comments

      If anyone is interested here is more modern and clear way of doing the same thing.

      #include <cmath>
      #include <cstdio>
      #include <vector>
      #include <iostream>
      #include <algorithm>
      
      using namespace std;
      
      int main() 
      {
      	int n, k;
      
      	cin >> n >> k;
      
      	vector<int> complenemts(k);
      
      	int count = 0;
      
      	int temp;
      	for (int i = 0; i < n; ++i)
      	{
      		cin >> temp;
      
      		int remainder = (temp % k);
      
      		int complenemt = (k - remainder) % k;
      
      		count += complenemts[remainder];
      
      		complenemts[complenemt] += 1;
      	}
      
      	cout << count;
      
      	return 0;
      }
      
      • SN
        plasmashadowx + 0 comments

        Could you please explain the aspect behind it.

      • Merter_Sualp + 2 comments

        That's great. My Java version is here:

        public class DivisibleSumPairs {
        
            public static void main(String[] args) {
                Scanner in = new Scanner(System.in);
                int n = in.nextInt();
                int k = in.nextInt();
                Map<Integer, Integer> buckets = new HashMap<>();
                int pairs = 0;
                for(int a_i=0; a_i < n; a_i++){
                    int num = in.nextInt();
                    num %= k;
        
                    int complement = (k-num) % k;
                    Integer count = buckets.get(complement);
                    if (count != null) {
                        pairs += count;
                    }
                    
                    count = buckets.get(num);
                    if (count == null) {
                        buckets.put(num, 1);
                    } else {
                        buckets.put(num, count+1);
                    }
                }
                System.out.println(pairs);
            }
        }
        
        • AG
          aman17 + 0 comments

          How does this solution take care of the condition i < j ?

        • DL
          daft_leech + 0 comments

          This is way simpler in Java 8

          return IntStream.range(0,n).map(x -> IntStream.range(x+1,n).map(y -> (ar[x]+ar[y])%k==0?1:0).sum()).sum();
          
      • DC
        Axesilo + 0 comments

        Yes, this is exactly the algorithm I came up with too. Wrote mine in Swift:

        import Foundation
        
        let readSplitter: () -> Array<Int> = { readLine()!.components(separatedBy: " ").map{Int($0)!}}
        
        let nk = readSplitter()
        let k = nk[1]
        let values = readSplitter()
        
        var buckets = [Int](repeating: 0, count: k)
        var pairCount = 0
        for value in values {
            let modded_value = value % k
            let complement = (k - modded_value) % k
            pairCount += buckets[complement]
            buckets[modded_value] += 1
        }
        print(pairCount)
        
      • CG
        chintanckg + 1 comment

        Can you place explain the logic.

        • jay209 + 3 comments
          public class 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[n];
                  int count = 0;
                  for(int a_i=0; a_i < n; a_i++){
                      int num = in.nextInt();
                      int remainder = num % k;
                      int complement = (remainder==0)?k:remainder;
                      count += a[k - complement];
                      a[remainder]++;
                  }
                  System.out.println(count);
              }
          }
          

          Perhaps this would be easy to understand for you. First of all we save the remainder and then we take its complement to make a pair. For example, in the sample test case, if the remainder is 1, then we will take its complement which is 2, and we will look for a number if divided, would give a remainder 2. Therefore, the sum of this pair will be divisible by 3 (which is k). Also, it gives O(n) solution.

          • TO
            tochicool + 0 comments

            Excellent solution and equivalent code; really helped my userstanding of the efficent solution!

            Note: There is a problem where you declare the size of the bucket array; it should be of size k, rather than n.

          • theshishodia + 0 comments

            Just had a small doubt, suppose the array is {15, 16, 17, 18, 19}, total size of 'a' will be 5. Now suppose k = 31. Then a[31 - 15] = a[16], which will be out of bounds. same will happen with a[15];

          • robertoxxx931 + 0 comments

            can anyone describe whats happening here step by step?

    • J
      jpan127 + 0 comments

      I did something like this for if k=3. Then realized k did not have to be 3 and gave up on that.

    • replytojain + 0 comments

      Here is an O(n) time solution. However, it does need O(n) space in worst case. Makes sense? Language: C#

      public static void CountMatch(int[] num, int k){      
              int count = 0;
              //store mod and such counts
              Dictionary<int,int> dict  = new Dictionary<int, int>();
                
              foreach(int n in num){
                int mod = n%k;
                int need = (k-mod) % k;
                  
                //check if the dictionary has the balance
                if(dict.ContainsKey(need)){
                    count += dict[need];
                }
                
                //increment/add mod to dictionary
                if(dict.ContainsKey(mod)){
                    dict[mod]+=1;
                }
                else{
                 dict.Add(mod, 1);    
                }
              }      
              Console.WriteLine(count);
          }
      
    • SG
      ghosh_saikat4000 + 0 comments

      Great solution ! Very elegant. Should be the editorial. Is there a similar solution if the question was to find divisible sum triplets ?

    • P
      prabuddha62 + 1 comment

      Why is the if case(if(k%2==0)) needed?

      • SG
        ghosh_saikat4000 + 0 comments

        Elements with a remainder of 0 mod k, are paired with elements in the SAME residue class. So, we shouldn't just multiply here because we will be overcounting. So, we need choose(m, 2), where m is the number of elements mod 0. I have implemented this logic in another way here ... https://www.hackerrank.com/challenges/divisible-sum-pairs/submissions/code/45490290

        Check it out. It might help.

    • LeHarkunwar + 1 comment

      How's this for python ?

      def divisibleSumPairs(n, k, ar):
          return sum(1 for i in range(n) for j in range(n) if i < j and (ar[i]+ar[j])%k == 0)
      
      • SD
        dheeraj13997 + 0 comments

        Hey, What you have added 1 in the sum?

    • akabeast + 1 comment

      I am missing something why is below two pieces of code different

      count += rem[k/2] * (k%2 == 0) ? (rem[k/2] - 1) / 2 : rem[k/2] - i;
      

      and

      if( k%2 == 0) count += (rem[k/2] * (rem[k/2]-1)) / 2;
      else count += rem[k/2] * (rem[k-i]);
      
      • SG
        ghosh_saikat4000 + 0 comments

        a*b/2 is different from a*(b/2)

        2*3/2 = 6/2 = 3

        2*(3/2) = 2*1 = 2

    • AB
      agnivabasak1 + 0 comments

      This solution seems really awesome to me ,but can someone please explain why the condition i!=k-1 is imposed(maybe with soem examples) .And also why and how the last condition(i.e , if(k%2==0)) implemented .Thanks!

    • codertoaster + 0 comments
      [deleted]
    • VA
      varun_1995 + 0 comments

      @usinha02 Your solution was really well thought out. Thanks.

    • alphazygma + 1 comment

      This is the Java implementation of usinha02, all credit goes to him and his algorithm.

      All I did is use another language and add comments for the community, as the solution was great but took me a while to understand each of the statements and why the last if was needed.

      static int divisibleSumPairs(int n, int k, int[] arr) {
          int pairCount = 0;
      
          // create an array with length equal to all reminders
          // available to k (0 to k-1 reminders)
          int[] remainderCountList = new int[k];
      
          for (int i = 0; i < arr.length; i++) {
              int remainder = arr[i] % k;
              remainderCountList[remainder]++;
          }
      
          // Now that the remainders have been counted, all that
          // produced a remainder of 0, can only be paired 
          // between themselves, so, if say, there were 4 
          // numbers, we can make up to six pairs 
          // i.e. (0,1) (0,2) (0,3), (1,2), (1,3), (2,3)
          int exactCount = remainderCountList[0];
          // all elements against a subset of one less of itself
          // and only half the pairs can be used
          pairCount += (exactCount * (exactCount-1)) / 2;
      
          // Now, for all other remainders, pairs are of those
          // that are complementing remainders
          // i.e. if K = 5, remainders would be 0, 1, 2, 3, 4
          // we know that 0 has already been accounted for
          // so, next pairs are all of those in 1 with 4 and
          // all those in 2 with 3
          // So we only need to iterate through half of the
          // remaining remainders, and make sure that we don't
          // use a reaminder against itself for this calculation
          for (int i = 1; i <= k/2 && i != k-i; i++) {
              pairCount += remainderCountList[i] * remainderCountList[k-i];
          }
      
          // Finally, there is one more case to consider, if K
          // yields an even number of remainders, the loop above
          // would have skipped the exact middle remainder.
          // i.e. for k = 4, remainders = 0, 1, 2, 3
          //   0 has been accounted for
          //   1 and 3 were paired up
          //   2 is missing
          // This last remainder behaves like the 0 remainder, 
          // so, we need to pair the numbers against themselves
          if (k % 2 == 0) {
              int halfCount = remainderCountList[k/2];
              pairCount += (halfCount * (halfCount-1)) / 2;
          }
      
          return pairCount;
      }
      
      • mahdijudeh + 0 comments

        Thank you for writing this out. Made me realize truly how great his was.

    • guner_batuhan + 0 comments

      i didnt understand your code. but here is another algorithm works with O(n)

      def search(numbers,k):
          numberofways=int()
          for i in range(len(numbers)-1):
              for j in range(i+1,len(numbers)):
                  if (numbers[i]+numbers[j])%k==0:
                      numberofways+=1
          return numberofways
      number=list()
      n=int(input())
      k=int(input())
      for i in range(n):
          number.append(int(input()))
      print(search(number,k))
      
    • TA
      tommyangkkasatr1 + 0 comments

      static int divisibleSumPairs(int n, int k, int[] ar) { // Complete this function int zero=0, one=0, two=0; for(int i=0;i

    • iceh22 + 0 comments

      Here is a Ruby version of your algorithm (where ar is the array of numbers):

      def divisibleSumPairs(n, k, ar)
          pairs = 0
          h = Hash.new(0).tap { |h| ar.each { |num| h[num%k] += 1 }}
          h.each do |key, val|
              compatikey = k - key
              compatival = h[compatikey]
              if key == compatikey || key == 0
                  pairs += ((1..(val-1)).inject(:+) || 1) if val > 1
              elsif compatival > 0
                  pairs += (val * compatival)
              end
              h.delete(key)
              h.delete(compatikey)
          end
          return pairs
      end
      
    • TB
      7u5h4r + 0 comments

      But you used much more space suppose k is 2^30 then a array would occupy much more space

    • blackjar72 + 0 comments
      [deleted]
  • WolfEng + 7 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 ;)

    • RB
      ronbeavers + 1 comment

      This is a really nice solution. I guess I was just hoping for a bit more clarity here. I see that you separate items into buckets and increment the count with the bucket. I'm curious though as to how this accurately gets number of items that are divisble evenly by k. Sorry if the question is basic, I haven't seen this done in this way before and I am attempting to re-learn algorithms.

      • WolfEng + 0 comments

        Uhm, let see, I'm guessing you're having trouble seeing how it manages to comply with the i < j rule. So, what does the rule really mean? It's only telling you that a value a[i] should not be paired with itself, and a tuple a[i],a[j] should not be considered twice so.. a[j],a[i] is not considered.
        You can think of this solution of only running forward, so a number a[i] appears always before a number a[j]. As it runs forward, for each number it looks for previous occurrences of its complement (it looks for the i's for a particular j).
        Say for instance if the divisor is 3, you could have this sequence:
        1, 2, 1

        1. The first is not matched with anything.
        2. The second is matched with the first. Although the 2nd could be matched with the 3rd, the algorithm isn't yet aware of the 3rd value...
        3. When the third value is read, it will be matched against the 2nd. Effectively matching the 2nd with the 3rd (remember a[i][j] and a[j][i] should only be counted once ;)

          I'm no algorithm guru, I had never seen this problem before... just started exercising for fun. But from my perspective there's no golden rule here, I don't see a generalization of this that's particularly valuable.
          If the intention is learning, I would recommend you to focus your energy in understanding more generalized forms of algorithms... these here are mostly "quizes", perhaps try an algorithms book to find generalized sets of problems and solutions.
          Also, many interesting real life problems are more about the data structures used and then the algorith comes natural to the data structure itself, so perhaps a focus on data structures is worth your while too...
          Of course, these quizes have a "fun" element, and exercising can really help in making the learning stick, so you could do both :P... just get the basics strong and then go for the corresponding quizes I guess.
    • thaihocmap123 + 0 comments

      Do we have to sum them up first and then we mod them?

      Please tell me why

    • KavinRanawella + 1 comment

      This solution is very nice. Because I got a longer piece of code. Good job.

      public static void main(String[] args) {
              Scanner in = new Scanner(System.in);
              int n = in.nextInt();
              int k = in.nextInt();
              int a[] = new int[n];
              for(int a_i=0; a_i < n; a_i++){
                  a[a_i] = in.nextInt();
              }
              
              int count=0;
              //checking aginst the condition
              for(int i=0;i<(n-1);i++){
                  for(int j=0;j<n;j++){
                      if(i<j){
                          if((a[i]+a[j])%k==0)
                              count++;
                      }
                  }
              }
              System.out.println(count); 
          }
      }
      
      • DC
        cys920622 + 1 comment

        Your i-loop terminates at < n-1 but your j-loop terminates at < n. Is there a possible Index out of bounds error there?

        Also you could save yourself a few iterations if every j-loop started at i+1. However this would not impact the O(n^2) time complexity.

        • KavinRanawella + 1 comment

          1.No there is no any error. I just want to omit the situation where i=n and j=n. That's all.

          2.That is a nice solution. Then u can directly skip the i>=j part. Thanks a lot.

          btw, can u explain the part u said "this would not impact the O(n^2) time complexity" please?

          • DC
            cys920622 + 0 comments

            Sure. What I meant is that even if you skip all 'j' values less than or equal to 'i', you will still have an O(n^2) time algorithm. In practice it will be a bit faster because you are 'skipping' some iterations, but strictly in terms of time complexity / running time, it is still the same O(n^2) time.

    • joris_suppers + 0 comments

      Nice I got something similar :)

      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 i=0; i < n; i++){
                  int remainder  = in.nextInt() % k;
                  int complement = (remainder == 0) ? 0:k-remainder;
                  count += a[complement];
                  a[remainder]++;
              }
              System.out.println(count);
          }
      
    • vivekwisdom + 0 comments

      Nice Explanation :)

    • DL
      daft_leech + 0 comments

      This is a way simpler solution with Java 8:

      return IntStream.range(0,n).map(x -> IntStream.range(x+1,n).map(y -> (ar[x]+ar[y])%k==0?1:0).sum()).sum();
      
    • EA
      sicter + 0 comments

      This confused me only because of the variable naming. I expected complement to be the bucket you need to check, when in actuality you must check k-complement. This assignment of complement made this solution make sense to me:

      int complement = number == 0 ? 0 : k-number;
      count += a[complement];
      
  • AS
    ShakeSaab + 7 comments

    Works fine in c++. Passes all tests.

    int n;
    int l;
    int count = 0;
    cin >> n >> l;
    vector<int> a(n);
    for(int i = 0;i < n;i++){
       cin >> a[i];
    }
    for(int i = 0;i < n;i++)
    {
        for(int k = i+1; k < n;k++)
        {
            if((a[i] + a[k]) % l == 0 && i < k)
                count++;
        }
    }
    cout << count;
    
    • DB
      dhb2411 + 0 comments

      You do not need to check for (i < k) because k is initialised as i+1.

    • Ghost_dsb + 0 comments

      you can restrict i to n-2 (ie i < n-1)

    • JS
      jitendra21 + 0 comments

      int main(){ int n; int k; cin >> n >> k; vector a(n); for(int a_i = 0;a_i < n;a_i++){ cin >> a[a_i]; } int count = 0;

      for(int i = 0; i < n; ++i)
      {
          for(int j = i+1; j < n; ++j)
          {
              if((a[i] + a[j]) % k == 0)
              {
                  ++count;
              }
          }
      }
      
      cout<<count;
      return 0;
      

      }

      No need for i < k check

    • S
      Sudarshan_P + 0 comments

      What is the need for (i

    • KF
      pkmuck33 + 3 comments

      This code will compile and run because c++ doesn't do bound checks on arrays. However you're accessing unknow memory in your code.

      for(int i = 0;i < n;i++)
      {
          for(int k = i+1; k < n;k++)
          {
          
          
      /*a[k] access unknown memory when "i = n-1". undefined behavior. It just happen to work in this instance.
      **/
              if((a[i] + a[k]) % l == 0 && i < k)
                  count++;
          }
      }
      
      • VK
        vasukapil2196 + 0 comments
        [deleted]
      • VK
        vasukapil2196 + 0 comments
        [deleted]
      • RS
        rheasanjan + 0 comments

        Why doesnt this logic work in C? I tried the same but I didnt get the right output.

    • M
      _MANU_ + 0 comments

      Not O(n) solution though......

    • rshaghoulian + 0 comments

      Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

      HackerRank solutions.

  • 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);
    }
    
    • NP
      naveenpragathesh + 1 comment

      Could you please explain this in detail? Mainly how we are finding the available pairs of given value in the above method

      • delight182 + 2 comments

        First of all, we need to notice that (A + B) % K = ([A/K] * K + A % K + [B/K] * K + B % K) % K = (A % K + B % K) % K (i.e. remainder of the sum equals to the remainder of the sum of the remainders). What it gives us is that in order to find B knowing A where (A + B) % K it's enough just to look at A % K and B % K.

        Then, consider we are at some item A[j] right now and we need to calculate how many pairs this A[j] makes with all the previous items A[i], i < j. That is actually a number of items A[i], i < j where A[i] % K complements A[j] % K. By "complements" here I mean that (A[i] % K + A[j] % K) % K == 0. That actually means that they are either both == 0 or their sum == K. (K - A[j] % K) % K effectively calculates this complement.

        Wrapping it up, we divide all the items in A into buckets by A[i] % K value. This gives us the ability at each step to see how many pairs we have involving some item A[i]. Iterating the array once and calculating only pairs on the left helps us not to count one pair two times while still covering all the combinations.

        Hope this helps.

        • NP
          naveenpragathesh + 0 comments

          Great explanation..Thanks a lot

        • rstormsf + 0 comments

          @delight182 Damn...I think I'm still confused about counts array and how those buckets work

    • SP
      thehoneymad + 0 comments

      This is definitely the best one here. The fact of actually getting the combination number by isolating each one of the input is absolutely brilliant.

    • MD
      mjdxn + 1 comment

      Despite the additional trick you've used, this solution's worst case runtime complexity is O(n+k), not O(n). The offender is this line:

      var counts = new int[k];

      C# has to initialize all k of those values to 0. While this may be fast on hardware, it still takes O(k) time in a standard model of computation.

      You could attempt to replace this with something like a hashtable/dictionary, but then you lose O(1) lookup + possible insertion time for each input element. If m is the total number of mod buckets encountered and it takes O(log(m)) time to insert/lookup, then the worst case runtime with this hashtable would be O(n*log(m)). This may or may not be an improvement over O(n+k) depending on how m and k compare to each other. You could run both approaches concurrently for O(min(n+k, n*log(m))) worst case time.

      Also keep in mind that the trick you are using here is effectively a trade-off in multiplications + a bitshift (for computing n'(n'-1)/2 for each bucket at the end) and distributing that computation via lookups and additions (over the n elements in the main loop). The multiplication approach will be faster at some point after where you exceed the word size of your architecture (after that point, we cannot assume that addition and multiplication are constant time operations).

      • delight182 + 1 comment

        Thanks for your valuable additions.

        To be honest I've never thought about how array initialization adds the computational complexity to the algorithm as a whole. And have never seen this idea in the books I've read (I'd be glad if you could recommend some literature that covers it at this level). Nevertheless my algorithm is defininely an algorithm that needs the array to be initialized, so your point is completely valid.

        The last point is completely valid too. It's just we had already had a multiplication version here, so I wanted to show more concise addition-only version.

        As for hashtable, could you elaborate on why you say hashtable has O(log(m)) insert/lookup time? I always thought it's amortized O(1). Otherwise I aggree that if the number of encountered buckets is much less than K then Hashtable variant will be preferable.

        • MD
          mjdxn + 1 comment

          The array allocation complexity has to do with the internals of the language/compiler. For a language like C#, that allocation operation has to go through chunks of the memory and forcibly set each element of the array to 0. Other languages or operators might do this lazily by just marking the start and end points of allocated memory. This is constant time with random access, but you cannot guarantee that all the elements are 0 (they are instead garbage values that are left over from whatever was in that memory location previously). You might find more details about this in a computer architecture or compilers textbook.


          Most hash table designs usually have a tradeoff between having constant worst case lookup and constant worst case insertion. Some designs do one or the other in constant worst case time while the other . I wrote "insertion/lookup" to encompass this. These tend to have a logarithmic worst case complexity for some operation, but also have an EXPECTED (not worst case) amortized constant runtime complexity (over uniformly random access sequences).

          • delight182 + 2 comments

            you cannot guarantee that all the elements are 0

            True, I was referring to this when I said that my algorithm definitely requires that all the counts are 0 at the beginning of the cycle (because we'll have reads before any writes). So it's not about computer architecture or compilers at all, it's about the algorithm itself - I'll still have to manually nullify the memory in not-nullifying-by-default language. Luckily in C# newarr opcode really translates to appropriate machine code.

            When I was referring to literature, I was saying that most common books/articles used for interview preparation will just skip array initializations when calculating time complexity, which I believe now is pretty superficial. I'd like to see a book that is not like that.

            As for hashtables, now I see I didn't pay attention you were talking about worst time. Thanks.

            • MD
              mjdxn + 0 comments

              it's not about computer architecture or compilers at all

              This is false. Both things significantly clarify what your algorithm is actually doing on the machine it is running on. It is equivalent to defining the model of computation that goes with your complexity measure. Some computations require more resources on some models of computation and fewer on others.

              not-nullifying-by-default language

              This property is enforced by the behavior of the C# compiler you are using. The fact that there is some gentleman's agreement to write all C# compilers the same way is irrelevant. Not all languages are lucky enough to have this. Some special architecture out there might allow you to zero out memory in constant time. A C# compiler could be modified to take advantage of this, which would allow your algorithm to truly be O(n) instead of O(n+k) without any edits.


              I'd like to see a book that is not like that.

              The interview prep materials I've seen are, indeed, all very hand wavey and superficial. I stand by my suggestion. Having additional knowledge of how your code works under the hood (i.e. what choices compilers make and how computation is done on your processor) will tell you exactly how complex (resource-wise) each operation is. I'm not aware of an alternative approach to get at what you want that does a better job of this.

            • DA
              askarovdaulet + 0 comments

              An interesting discussion. I actually agree with you at this point, that this is about the algorithm itself. The complexity will be O(n+k) here regardless of the language you use, unless you have some magical infinite memory all initialized with zero bits. Then you can do some simple arithmetic and allocate properly initialized memory instantly independent of the value of k.

              Now, the actual constants hidden in the O(n+k)~alpha*n+beta*k, in particular beta will obviously depend on the language, compiler, operating system, etc... And in case of instantiation beta should be pretty small already.

              Regarding lazy initialization, it will not be helpful here, since you rely on the values being zero on your first lookup. If one insists on lazy array, another boolean array of size k is needed to keep track of which entries of the integer array were already incremented/touched by the algorithm. But all entries of this boolean array of size k itself have to be initialized to false, the problem becomes circular. Seems like there is no way around the O(n+k) from the computer science perspective.

              Regarding the general downsides of this algorithm, I think the space requirement is a much more serious issue. Consider this case n=2, k=2e10, a = [1,2]. A simple O(n^2) will solve this very quickly, while the bucket approach might stall on trying to create an array of integers of size k. So, it might be a good idea to first check the values of n and k and branch into two different approaches based on the value of k. This is what library sorting algorithms do frequently.

    • W
      wibgyor + 0 comments
      [deleted]
    • patelurvil38 + 0 comments
      count += counts[(k - bucket) % k];
              counts[bucket]++;
      

      What is this two lines mean?can you explain in brief?

    • JaroslavPernica + 0 comments

      I did O(n) in js using Maps. I iterate over numbers a and then calculate mod and complementary to the mod needed for the sum equal k. then i save complementary to hashmap and the value in the hashmap means how many numbers could make the pair. Since hashmap get and set are O(1) i assume i have O(n).

      function divisiblesumpairs (n, k, a) {
      	let compls = new Map(),
      	count = 0;
      
      	for (let i = 0; i < n; i++) {
      		let m = a[i] % k,
      			c = (k - m) % k,
      			p, q;
      
      		if (p = compls.get(m))
      			count += p;
      		
      		if (q = compls.get(c))
      			compls.set(c, ++q)
      		else
      			compls.set(c, 1)
      	}
      	return count;
      }
      
    • glukki + 0 comments

      Oh man, this solution is much better, but underrated! Reading of buckets explanation in more popular comments on top I had a feeling, that complexity can be reduced even more, and calculation made just with 1 loop. Thank you!

  • rshaghoulian + 3 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

    import java.util.Scanner;
    
    public class Solution {
        public static void main(String[] args) {
            Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
            int k = scan.nextInt();
    
            int [] modBucket = new int[k];
            int count = 0;
            for (int i = 0; i < n; i++) {
                int modValue = scan.nextInt() % k;
                count += modBucket[(k - modValue) % k];
                modBucket[modValue]++;
            }
           
            scan.close();
            System.out.println(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
    
    • EM
      EvanMJ + 1 comment

      Can someone please explain. I read the comment fully but I'm lost!

      • rshaghoulian + 1 comment

        Hi. I added a detailed explanation to my original post to help clear up any confusion.

        HackerRank solutions.

        • K
          andromeda3107 + 1 comment

          Thank you for the great solution. I think you should mention the following property of modulus in your comment for more clarity:

          (a+b)%n=(a%n+b%n)%n

          • rshaghoulian + 1 comment

            Hmmm. That equation you put is correct. However, it complicates the logic for me a bit as it makes more sense to me as (a+b)%n.

            • BS
              bhawana053 + 1 comment

              how does your solution ensure i < j for every pair ?

              • rshaghoulian + 1 comment

                The question asks to print pairs, for every i < j, where a_i + a_k is divisible by k. This constraint was placed in the problem so that we count pairs just once. For example, we want to count (a_i, a_j), but not also (a_j, a_i).

                My solution counts each pair once. This is achieved by looping linearly through the input, and comparing each number to previous numbers only.

                HackerRank solutions.

                • BS
                  bhawana053 + 0 comments

                  Thank you.

    • OA
      alfredooctavio + 1 comment

      Great job. I would like to ask you where you find this kind of logic? I saw that you have knowledge about algorithm efficiency. Can you suggest me some books that I can read, my code solution was good but yours is better. My best regards!

      • rshaghoulian + 1 comment

        There are some tricks that are handy to know. I think this is called bucket sort and it's a good one to memorize, so you can apply to new problems in the future.

        I think I came across this trick when learning about sorting algorithms (Such as QuickSort and MergeSort). Wikipedia might have some good summaries and pseudocode for various sorts.

        HackerRank solutions.

        • OA
          alfredooctavio + 0 comments

          I really appreciate your comment. Thank you.

    • SM
      BitL0rd + 0 comments
      [deleted]
  • NYJ1qCr + 2 comments

    Use Python 3:

    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    b = [[c, d] for x, c in enumerate(a) for y, d in enumerate(a) if x < y and (c + d) % k == 0]
    print(len(b))
    
    • SW
      sowerk + 7 comments

      Slightly more pythonic:

      res = sum((i+j)%k == 0 for x, i in enumerate(a) for j in a[x+1:])

      Since True == 1

      • afif_benmati + 0 comments

        brilliant!

      • udaykumar_uk245 + 1 comment

        Can you explain me your Code.

        • TL
          asperatology + 1 comment

          res is the result.

          sum() sums up all of the elements that matches the condition, (i+j)%k==0, and the elements are gathered from pair (x,i).

          enumerate(a) returns multiple pairs, (x, i), where x is the index of the element, and i is the element value itself, for each element in the array a. That also means j is the element in the array a where the index is x+1 or to the right of a[x] by 1. In short, i is a[x] and j is a[x+1].

          So, you have the array elements, i, and j. Given that when iterating through the array a, the (i+j)%k==0 then becomes something similar to the following sequence, due to True being evaluated as 1:

          0, 0, 1, 0, 0, 0, 1, 0, ...

          Which when calling on sum(), will give you the total count of those that satisfied the condition (i+j)%k==0.

          res = 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + ...

          • udaykumar_uk245 + 0 comments

            Thank you

      • AG
        guptaayush241 + 0 comments

        Hats off man!

      • ameykulkarni + 0 comments

        Please change your name from sowerk to pythonKing

      • M
        msambitkumar1991 + 1 comment

        Nice logic :)

        • udaykumar_uk245 + 0 comments

          Thank you

      • A
        tadamori_yoshi + 1 comment

        I went slightly different way

        n, k = list(map(int, input().split()))
        a = list(map(int, input().split()))
        print (sum([(a[i]+a[j])%k==0 for i in range (n) for j in range(i+1,n)]))
        
        • DA
          askarovdaulet + 0 comments

          You can forego list() call on the first line since you immediately proceed to multiple assignment without using any list-specific methods.

          I also used range() in my solution since it's a generator in Python 3, which saves memory as opposed to slicing a[i+1:] which copies the references (8 bytes each) of the sliced portion of list. But in Python community this might be called premature optimization :)

      • DA
        askarovdaulet + 0 comments

        Very nice! A couple of things that I could suggest is changing the names of the variables for clarity, since people typically use i and j for indexing and x for the iterable values:

        res = sum((ai+aj)%k==0 for i,ai in enumerate(a) for aj in a[i+1:])
        

        Another optimization is using islice, which though slightly sacrificing readability improves the performance since slicing is not memory or time efficient in this case.

        res = sum((ai+aj)%k==0 for i,ai in enumerate(a) for aj in islice(a,i+1,n))
        
    • rshaghoulian + 0 comments

      Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

      HackerRank solutions.

  • KL
    kzliu + 2 comments

    python solution

    print(sum([1 for i in range(n) for j in range(i) if (a[i]+a[j])%k==0]))
    
    • DA
      askarovdaulet + 0 comments

      Nice. It took me a few seconds to realize that range(i) can work here instead of range(i+1,n). You just look at all the same combinations in different order.

    • rshaghoulian + 0 comments

      Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

      HackerRank solutions.

  • JC
    jcatalanolmos + 2 comments

    My solution on python3:

    from itertools import combinations

    print(sum([1 for i,j in combinations(a,2) if (i+j)%k ==0]))

    • pranavdave + 0 comments

      Awesome !!

    • rshaghoulian + 0 comments

      Nice job. Your solution is O(n^2). If you're interested in a challenge, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

      HackerRank solutions.

  • zarrellab + 1 comment

    Easy to read python solution using itertools and list.count() method:

    from itertools import combinations
    
    pairs = [sum(pair) % k for pair in combinations(a, 2)]
    print(pairs.count(0))
    
    • rshaghoulian + 0 comments

      Nice job. Your solution is O(n^2). If you're interested in a challenge, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

      HackerRank solutions.

  • PD
    pravd + 1 comment

    public class 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[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i; j < a.length - 1; j++) {
                if ((a[i] + a[j + 1]) % k == 0) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
    

    }

    • rshaghoulian + 0 comments

      Nice job. Your solution is O(n^2). If you're interested, try this more efficient O(n+k) solution using buckets. I think buckets are a very cool concept.

      HackerRank solutions.