XOR

[hacker9876]

find the number of pairs (i,j) such that 1≤i<j≤N and the bitwise XOR of Ai and Aj can be written as a sum of two (not necessarily different) prime numbers with the same parity (both odd or both even).Here parity means either if number can be written as sum of both even and both odd numbers.Can anyone suggest me better way of doing this problem???

t = int(input())
while t!=0:
	n = int(input())
	a = list(map(int,input().split()))
	h=0
	for i in range(n-1):
		for j in range(i+1,n):
		    v = a[i]^a[j]
		    if (v!=2) and (v%2==0) and v!=0:
		        h+=1
	print(h)
	t-=1

[TheIdeasMan]

A better way than what? This is not a homework site. Post your code then someone may help.

[hacker9876]

i just posted my solution can you tell me better way of doing this problem

[JLBorges]

n = int( input() )

cnt = 0

for i in range(n-1):
   for j in range( i+1, n ):
       if (i^j)%2 == 0: cnt = cnt + 1
           # Goldbach's conjecture 
           # https://en.wikipedia.org/wiki/Goldbach%27s_conjecture#Verified_results

print(cnt)

[jonnin]

hint: what values can the xor result be? is it all the numbers up to N, with a couple of exceptions?
if that is true, then the question is what numbers can be written as a sum .... etc...
now what do we know about adding numbers of the same parity? 1+1 =2. 3+3 = 6. 7+3 = 10. Hmm ... sum of odds is even. 2+2 = 4. 10+4 = 14. Hmm, sum of evens is even. No need to check half the values, right?

look for other math properties of primes and xors to see if you can find additional truths that reduce processing.

[hacker9876]

time limit is too high for my solution can anyone suggest me a better way of solving this problem

[mjvns]

XOR of Even and Odd will always produce an Odd number and Odd number cannot be expressed as sum of two primes of same parity.
Now, if both the numbers are even numbers or if both the numbers are odd, then if the difference of these numbers is greater than 2, then the XOR will necessarily give an even number >2 which can be expressed as a sum of two primes of same parity.

Now, if the difference of both the numbers is exactly equal to 2, then if both the numbers are even, consider the larger number, express it in binary representation. If the least two significant bits turn both 0. Then, the XOR of the number will give an even number greater than 2 that can be expressed as sum of two primes of same parity. Similarly, if both the numbers are odd, then consider the larger number and express it in binary. Consider the least two significant bits. If the least significant bit is 1 and the bit preceding the least significant bit is 0, then the XOR will give an even number which can be expressed as the sum of two primes.

Thus, we need only the two least significant bits to decide the solution.

[pawan12]

Its really shameful to ask on-going contest(Codechef September challenge) solution.You can ask it after the contest ends.