Divisible Sum Pairs

user_5362583 0
Viewed 5202

Though it will be weird to see this question but I really need to understand some core concepts while I continue my journey of coding. I have a problem which is on Hackerrank it goes like : DIVISIBLE SUM PAIRS

I will anyhow give the problem statement here:

Problem Statement

Given an array, where we have to find the number of pairs divisible by the the given number k, and there is one more condition to it, which is : the arr[i] < arr[j] from those pairs.

Example

For example, ar=[1,2,3,4,5,6] and k=5. Our three pairs meeting the criteria are [1,4] [2,3] and [4,6].

Code

Before I publish my code, I would like to tell you that my code has passed all the test cases, and it is accepted to move ahead to the next challenge, but there is a glitch which I'm trying to figure out, which is there in the code. 

static int divisibleSumPairs(int n, int k, int[] ar) {
    int count = 0;
    for(int i=0; i<ar.length; i++){
      for(int j=i+1; j<ar.length; j++){
            if(((ar[i]+ar[j])%k)==0){
                if(i < j)
                   count++;
            }
        }
    }
    return count;
}

In here when I do this if(i < j) count++, it gives me the correct result, but as soon as I do this if(ar[i] < a[j]) count++, it is supposedly giving me a wrong answer.

Can anybody help me clearing this out, like what is left. Since I know the check arr[i] < arr[j] should give the correct result. I don't want to proceed with the wrong knowledge.

EDITS

Since I have understood what I was doing wrong. And I have one edits in my code that is not starting the inner loop with 1, since it will start off with 1 every time the inner loop finishes, and again runs. I thank everyone who helped me clearing this and making my concepts strong enough to deal the questions like this.

I personally thank Mike 'Pomax' Kamermans, Ricola, and xerx593 for clearing out my doubts, and giving me the core concepts of looping through the elements. It will help me in future, and I won't repeat that thing again. :)

arrays java
5 Answers

I just checked your link and the condition given in the question statement is

Find and print the number of (i,j) pairs where i < j and ar[i] + ar[j] is divisible by k.

Which is simply the number of unordered pairs of elements for which the sum is divisible by k.

However you wrote

there is one more condition to it, which is : the arr[i] < arr[j] from those pairs.

I seems like you have misread the question. And it explains why the i<j condition works whereas arr[i] < arr[j] doesn't.

Now that you know that you only need the unordered pairs, no need to iterate j from 1 to ar.length. Since you need j > i, every j between 1 and i (inclusive) is useless. You can simplify your code to:

static int divisibleSumPairs(int n, int k, int[] ar) {
    int count = 0;
    for(int i=0; i<ar.length-1; i++){
      for(int j=i+1; j<ar.length; j++){
            if(((ar[i]+ar[j])%k)==0){
                   count++;
            }
        }
    }
    return count;
}
user_74249480

Wen you do i = {0 ... 10} and j = {1 ... 10}, then there are (about) 100 cmobinations (of i and j), (about) 50, where i < j and the rest vice versa. So your assumption is wrong, that:

it is supposedly giving me a wrong answer

...it gives you correctly the wrong answer! ...since when a[i] + a[j] % k == 0, then a[j] + a[i] % k == 0 also!

If you don't include the if(i < j), you count (the occurrence of pairs ..exactly) doubly.

An (implementation) alternative would be:

for (int i = 0; i < ar.length; i++) {
  // ensure i < j via initialization ;)
  for (int j = i + 1; j < ar.length; j++) {
    if (((ar[i]+ar[j]) % k) == 0) {
      counter++;
    }
  }
}

...to initialize the inner loop with i + 1 instead of 1.

EDIT:(after getting the question better)

Your assumption, that a[i] > a[j] is equivalent with i > j OR j < i(but not both), is almost correct: except when a[i] == a[j].

user_5923550

This solution is using javaScript : 

 divisibleSumPairs (n, k, ar) => {
  let count = 0;
  ar = ar.map((value, index, arr) => {
    for (let i = index + 1; i <= arr.length; i++) {
      if ((value + arr[i]) % k === 0) {
        count++;
      }
    }
  });
  return count
}
user_112548260

That's my solution in javaScript (Passed all test-cases):

function divisibleSumPairs(n, k, ar) {
    let count=0;
    
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            if(i<j){
              if((ar[i]+ar[j])%k===0) count++; 
            }
        }
    }
    return count;
}
user_145921460

A solution in Python 3 (Passed all test-cases):

The itertools.combinations(arr,r) returns the r length subsequences of elements from the input iterable. Combinations are emitted in lexicographic sort order. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

from itertools import combinations

def divisibleSumPairs(n,ar,k):
    pairs = []
    for com in combinations(ar,2): 
        if sum(com) % k == 0:
            pairs.append(com)
    return len(pairs)


nk = input().split()
n = int(nk[0])
k = int(nk[1])            
ar = list(map(int, input().rstrip().split()))
print(divisibleSumPairs(n,ar,k))
user_119703220
Related