Divisible Sum Pairs

Question

Though it will be weird to see this question 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 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 that 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;
}

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 supposedly gives me a wrong answer.

Can anybody help me clear 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 edit 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 clear this and made my concepts strong enough to deal with 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 the future, and I won't repeat that thing again. :)

Answer 1

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

Answer 2

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