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; }
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 ;)
The main trouble with hackerrank problems is the way the problem is explained, poorly explained. It takes half an hour to get what it requires but 5 mins to code ((
Simple and efficient O(n+k) solution
From my HackerRank solutions which contains additional comments in code.
Runtime: O(n + k), by doing only 1 pass of the values
Space Complexity: O(k)We keep track of the mod values in buckets for each number we read. We can do this by creating k buckets where bucket i counts each number n where n % k = i.
Notice that each bucket has a corresponding complement bucket. That is, if we take the mod value of one bucket and add it to the mod value of another bucket, we get k.
Bucket Complement Bucket ------ ----------------- 0 0 1 k-1 2 k-2 3 k-3 ...... k-3 3 k-2 2 k-1 1
As we come across each number, we find its corresponding complement bucket. Each number in this complement bucket can be paired with our original number to create a sum divisible by k
static int divisibleSumPairs(int n, int k, int[] ar) { int [] bucket = new int[k]; int count = 0; for (int value : ar) { int modValue = value % k; count += bucket[(k - modValue) % k]; // adds # of elements in complement bucket bucket[modValue]++; // saves in bucket } return count; }
Sample Bucket placement
For the following sample input
6 3 1 3 2 6 1 2
We have
Bucket Integers Count ------ -------- ----- 0 3, 6 2 1 1, 1 2 2 2, 2 2
For Python Lovers
def divisibleSumPairs(n, k, ar): # Complete this function count = 0 for i in range(n-1): j = i+1 while j < n: if ((ar[i] + ar[j]) % k) == 0: count += 1 j += 1 return count
Sort 1857 Discussions, By:
Please Login in order to post a comment