Divisible Sum Pairs

usinha02 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 Can you please explain the logic here of how did you deduce the total number of pairs modding to k?
petreeftime 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 Thanks this lays it down pretty good. This should be in the editorial.
danjb 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.
petreeftime Yes, but this second solution is a better learning tool for modular arithmetics. The other solution is trivial.
aarohiagarwal12 Don't you think this might increase the space complexity if k>10 or something..??
lovereli There is always a tradeoff between space and time complexity. Otherwise we might be in a better world!!
Jyothi_sirigi But in the problem it is given as we have to print the number of (i,j) pairs and the given condition is i
Khoa190602 It said to print the number of pairs not the pairs themselves
kiamottullah hey please tell me that which algorithom or any other books are u flowing >?
prakashk885 [deleted]Jlookup 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 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 [deleted]surajt_oneliner fab man :)
LeHarkunwar 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)
ghosh_saikat4000 It's quadratic ... Less lines of code doesn't necessarily mean less time complexity.
malexand314 It's the exact same solution as above from SebastianNielsen, just in a one-line format.
Ravitejacms Awesome!!
washinpi 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 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 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 [deleted]LukeRocheDev 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++; } }
bytes_and_bits It does not pass all test cases
correia_mario [deleted]correia_mario [deleted]
correia_mario 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 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 Why are we substracting 1 from the array length in the first loop?
juri_the_eagle Cause the second number has to be at a later position, there's never a pair for the last position.
chinmay43 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 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
Token_404 [deleted]toosengzhao Could you provide some explanations to this? Appreciate it lots!
djaychela 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.
felix_jatmiko The second step exists because ((k - modu % k) + (modu % k)) % k == 0.
nivedpk1994 brilliant logic
djaychela 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 God
amaals_emam count += int(mods[0] * (mods[0] - 1) / 2) from where did this equation come up?
rajusujan2020 because n*n-1/2 pairs are available
aarohiagarwal12 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)
dtyagi1 print sum(1 for i in itertools.combinations(ar,2) if sum(i)%k==0)
Dimple151997 can u explain the code
rahulrajpl 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
smdaziz Thanks for the explanation petreeftime! How does it take care of choosing only those pairs whose index i < j?
tanzeelosama GENIOUS!
vikki_kumar Thanks this is really helpfull.
ShikamaruNara 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 ??
sri_sam229 good logic but i am interested to know if that helped any complexity.
ShivendraKadam Nice explaination Thank You
kharatpriyank 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 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?
ghcho20 [deleted]
delight182 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 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 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!
de_ganxta thanks
ghcho20 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).petreeftime 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.
ghcho20 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 ?
thanksantipyrrhus 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 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 [deleted]tourofer [deleted]abhilashpani651 it displays floating point exception
jay209 It has O(n^2) complexity!
prabhjot8126 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++; } } }
hira89 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.
prabhjot8126 @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 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++; } }
dinesh_pi these can only find consecutive pairs
prasanna_STR I thinks its wrong
anshumanc007 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 Also check for the condition where i < j then increment the count variable.
jyoshu [deleted]
mikepare93 I did something similar and passed. I'm pretty sure this type of solution is O(nlogn).
varun_1995 run outer loop for i < n - 1
logasanjayr5055 this will eliminate the comparison of certain numbers
anicse0904071 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 [deleted]erichamion 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); }
burak54 My eyes bleed. Too much comment lines.
bozhko_maksim_s1 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; }
plasmashadowx Could you please explain the aspect behind it.
Merter_Sualp 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); } }
aman17 How does this solution take care of the condition i < j ?
daft_leech 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();
Axesilo 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)
chintanckg Can you place explain the logic.
jay209 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.
tochicool 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 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 can anyone describe whats happening here step by step?
jpan127 I did something like this for if k=3. Then realized k did not have to be 3 and gave up on that.
replytojain 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); }
ghosh_saikat4000 Great solution ! Very elegant. Should be the editorial. Is there a similar solution if the question was to find divisible sum triplets ?
prabuddha62 Why is the if case(if(k%2==0)) needed?
ghosh_saikat4000 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 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)
dheeraj13997 Hey, What you have added 1 in the sum?
akabeast 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]);
ghosh_saikat4000 a*b/2 is different from a*(b/2)
2*3/2 = 6/2 = 3
2*(3/2) = 2*1 = 2
agnivabasak1 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 [deleted]varun_1995 @usinha02 Your solution was really well thought out. Thanks.
alphazygma 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 Thank you for writing this out. Made me realize truly how great his was.
guner_batuhan 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))
tommyangkkasatr1 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 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
7u5h4r But you used much more space suppose k is 2^30 then a array would occupy much more space
blackjar72 [deleted]
WolfEng 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 ;)
ronbeavers 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 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 valuea[i]
should not be paired with itself, and a tuplea[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 numbera[i]
appears always before a numbera[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- The first is not matched with anything.
- 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...
- When the third value is read, it will be matched against the 2nd. Effectively matching the 2nd with the 3rd (remember
a[i][j]
anda[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 Do we have to sum them up first and then we mod them?
Please tell me why
KavinRanawella 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); } }
cys920622 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.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?
cys920622 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 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 Nice Explanation :)
daft_leech 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();
sicter 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];
ShakeSaab 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;
dhb2411 You do not need to check for (i < k) because k is initialised as i+1.
Ghost_dsb you can restrict i to n-2 (ie i < n-1)
jitendra21 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
Sudarshan_P What is the need for (i
pkmuck33 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++; } }
vasukapil2196 [deleted]vasukapil2196 [deleted]rheasanjan Why doesnt this logic work in C? I tried the same but I didnt get the right output.
_MANU_ Not O(n) solution though......
rshaghoulian 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.
delight182 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); }
naveenpragathesh Could you please explain this in detail? Mainly how we are finding the available pairs of given value in the above method
delight182 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 atA % K
andB % K
.Then, consider we are at some item
A[j]
right now and we need to calculate how many pairs thisA[j]
makes with all the previous itemsA[i], i < j
. That is actually a number of itemsA[i], i < j
whereA[i] % K
complementsA[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 byA[i] % K
value. This gives us the ability at each step to see how many pairs we have involving some itemA[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.
naveenpragathesh Great explanation..Thanks a lot
rstormsf @delight182 Damn...I think I'm still confused about
counts
array and how those buckets work
thehoneymad 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.
mjdxn 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 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.
mjdxn 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 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.
mjdxn 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.
askarovdaulet 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.
wibgyor [deleted]patelurvil38 count += counts[(k - bucket) % k]; counts[bucket]++;
What is this two lines mean?can you explain in brief?
JaroslavPernica 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 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 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
EvanMJ Can someone please explain. I read the comment fully but I'm lost!
rshaghoulian Hi. I added a detailed explanation to my original post to help clear up any confusion.
andromeda3107 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 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.
bhawana053 how does your solution ensure i < j for every pair ?
rshaghoulian 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.
bhawana053 Thank you.
alfredooctavio 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 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.
alfredooctavio I really appreciate your comment. Thank you.
BitL0rd [deleted]
NYJ1qCr 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))
sowerk 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 brilliant!
udaykumar_uk245 Can you explain me your Code.
asperatology 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)
, wherex
is the index of the element, andi
is the element value itself, for each element in the arraya
. That also meansj
is the element in the arraya
where the index isx+1
orto the right of a[x] by 1
. In short,i
isa[x]
andj
isa[x+1]
.So, you have the array elements,
i
, andj
. Given that when iterating through the arraya
, the(i+j)%k==0
then becomes something similar to the following sequence, due toTrue
being evaluated as1
: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 Thank you
guptaayush241 Hats off man!
ameykulkarni Please change your name from sowerk to pythonKing
msambitkumar1991 Nice logic :)
udaykumar_uk245 Thank you
tadamori_yoshi 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)]))
askarovdaulet 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 :)
askarovdaulet 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 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.
kzliu python solution
print(sum([1 for i in range(n) for j in range(i) if (a[i]+a[j])%k==0]))
askarovdaulet 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 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.
jcatalanolmos My solution on python3:
from itertools import combinations
print(sum([1 for i,j in combinations(a,2) if (i+j)%k ==0]))
pranavdave Awesome !!
rshaghoulian 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 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 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.
pravd 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 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.
Sort 429 Discussions, By:
Please Login in order to post a comment