## Divisible Sum Pairs

Sort 429 Discussions, By:

# 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;
}


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

• P

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

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

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..??

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

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

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

• PK
[deleted]
• JT

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)


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)

[deleted]

fab man :)

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

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

• MA

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

• RT

Awesome!!

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)


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])


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++;
}}
}
}

[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

It does not pass all test cases

• C
correia_mario + 1 comment
[deleted]
• C

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;


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


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

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

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))


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
[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

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

• NP

brilliant logic

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.

God

• AE
amaals_emam + 1 comment

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

• PK

because n*n-1/2 pairs are available

• AA

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

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

• DG

can u explain the code

• RR

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

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

GENIOUS!

• VS

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

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

Nice explaination Thank You

• PK

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;


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
[deleted]

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!

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

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

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)

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++;

}
}
}
}


}

[deleted]
[deleted]

it displays floating point exception

It has O(n^2) complexity!

• PS

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

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

@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);

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

these can only find consecutive pairs

• PK

I  thinks its wrong

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?????

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

• JS
[deleted]

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

• VA

run outer loop for i < n - 1

• LS

this will eliminate the comparison of certain numbers

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 .

[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.

// 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.
.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

My eyes bleed. Too much comment lines.

• MB

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

Could you please explain the aspect behind it.

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

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

• DL

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

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

import Foundation

let k = nk[1]

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.

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

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.

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];

can anyone describe whats happening here step by step?

• J

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

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];
}

if(dict.ContainsKey(mod)){
dict[mod]+=1;
}
else{
}
}
Console.WriteLine(count);
}

• SG

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

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

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

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

2*3/2 = 6/2 = 3

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

• AB

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!

[deleted]
• VA

@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;
}


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

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

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

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

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

[deleted]

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.

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.

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

• 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

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.

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);
}


Nice Explanation :)

• DL

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

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

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

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

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

• JS

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

What is the need for (i

• KF

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
[deleted]
• VK
[deleted]
• RS

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

• M

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

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.

My O(n) C# solution:

static void Main(String[] args)
{
.ToArray();
int n = nk[0];
int k = nk[1];
.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

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

Great explanation..Thanks a lot

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

• SP

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

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.

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).

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

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

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
[deleted]
count += counts[(k - bucket) % k];
counts[bucket]++;


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

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;
}


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!

### Simple and efficient O(n+k) solution

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.

• 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.

• BS

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.

• OA

I really appreciate your comment. Thank you.

• SM
[deleted]

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

Slightly more pythonic:

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

Since True == 1

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 + ...

Thank you

• AG

Hats off man!

• M
msambitkumar1991 + 1 comment

Nice logic :)

Thank you

• A

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

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

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))


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.

• KL

python solution

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

• DA

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.

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.

• JC

My solution on python3:

from itertools import combinations

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

Awesome !!

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.

• 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))


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.

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


}