1

"You are given an array of n integers and an integer k. Find and print the number of (i,j) pairs where i<j and a[i] + a[j] is evenly divisible by k."

Sample input would be:

6 3
1 3 2 6 1 2

where 6 is n, 3 is k and the second line is the array of integers. The output for this input would be 5.

Here is my code, but i am not passing the test cases and am almost positive it has to do with how i am indexing it.

import sys


n,k = input().strip().split(' ')
n,k = [int(n),int(k)]
a = [int(a_temp) for a_temp in input().strip().split(' ')]

count=0;

for i in range(n):
    curr = n-i
    for j in range(curr):
        if i < i + j:
            if k % (a[i] + a[i+j]) ==0:
                count = count + 1

print(count)

Also, followup question: Is this method i am approaching an efficient way of going about it?

Improve this question
2
  • you are using i+j in your code as the j in the question, right? If yes, you are solving it not for i<i+j but for i<=i+j.You also you need to move the k to the right hand side when checking for divisibility Commented Nov 2, 2016 at 4:51
  • 2
    I'm not sure if for j in range(curr): is good. I would do rather for j in range(i+1, n): This i < i + j: you can write as 0 < j. This is wrong k % (a[i] + a[i+j]) == 0 - you need (a[i] + a[i+j]) % k == 0. Besides I would use for i in range(n-1): (without last element - you don't have to compare last element with last element) Commented Nov 2, 2016 at 4:52

3 Answers 3

Reset to default
2

you can try this ...

import sys 
n,k = input().strip().split(' ') 
n,k = [int(n),int(k)] 
a = [int(a_temp) for a_temp in input().strip().split(' ')]        
print(sum([1 for i in range(n) for j in range(i) if (a[i]+a[j])%k==0]))
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

You can remove [] in the sum and use it like a generator as in sum(1 for i in range(n) for j in range(i) if (a[i]+a[j])%k==0)
Can you explain what is going on in the print statement? What does it mean "1 for i" and why "for j in range (i)"?
'1 for i' is use when if condition is true then it append 1 in list and at the end we take the sum of list which gives the count of pairs. 'for j in range i' is use to check all pairs with i< j condition
Also, how is that line of code checking to see if i < j ?
For more about list comprehensions please visit python-3-patterns-idioms-test.readthedocs.io/en/latest/…
2
  • k % ... means "k is divisible by ...", not "... is divisible by k".
  • if i < i + j is not very useful; you're better off doing what furas recommends in comments.
Improve this answer

5 Comments

Wow, duh! Thank you so much!
Your code also accepts the cases where i==j You need to fix your loop too
Yea, i did in my submitted code. What is wrong with the loop? Do you just mean the i==j case?
I wrote something else when @furas didn't comment yet. If he makes his comment into an answer, you should totally choose him (or Aman) over me.
Okay i will. Very noble of you Amadan
0

What you need is to make use of itertools.combinations:

from itertools import combinations

count = 0
for i, j in combinations(range(n), 2):
    if i < j and (a[i] + a[j]) % k == 0:
        print i, j
        count += 1

Discussion

  1. range(n) returns a list of indices 0 .. n-1
  2. combinations(range(n), 2) will yield a list of two indices (without duplications)
  3. (a[i] + a[j]) % k == 0 is the test that your asked
  4. Note that combinations will yield pairs of i, j where i is always less than j, but the test i < j is there as a paranoid measure
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.