Header Ads Widget

War of XORs | codechef solution

Rajnish Tripathi 21:14

Chef is stuck at the following problem. Help him solve it!

Chef has a sequence of integers �1,�2,…,��. He should find the number of pairs (�,�) such that 1≤�<�≤� and the bitwise XOR of �� and �� can be written as a sum of two (not necessarily different) prime numbers with the same parity (both odd or both even).

Input

  • The first line of the input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • The first line of each test case contains a single integer �.
  • The second line contains � space-seprated integers �1,�2,…,��.

Output

For each test case, print a single line containing one integer — the number of valid pairs.

Constraints

  • 1≤�≤10
  • 1≤�≤105
  • 1≤��≤106 for each valid �

Subtasks

Subtask #1 (10 points): 1≤�≤103

Subtask #2 (90 points): original constraints

Sample 1:

Input
Output
1
5
2 4 8 1 3
3

Explanation:

Example case 1: The three valid pairs are (1,2), (1,3) and (2,3). For example, �1⊕�2=2⊕4=6=3+3.

 Code(C++):-

#include <iostream>

using namespace std;

typedef long long ll;

const int M = 1000010;
ll t,n,x,e,o,s,a[M];

int main() {
cin >> t;
while (t--) {
cin >> n;
s = 0, e = 0, o = 0;
for (int i = 0; i < M; i++) a[i] = 0;
for (int i = 0; i < n; i++) {
cin >> x;
a[x]++;
if (x%2) o++;
else e++;
}
for (int i = 1; i < M-4;i++) s += a[i]*((i%2?o:e)-a[i]-a[i^2]);
cout << s/2 << endl;
}
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine()),n,max,x;
        long o,c,y;
        while(t-->0)
        {
         n=Integer.parseInt(br.readLine());
         String s[]=br.readLine().split(" ");
         int a[]=new int[1000003];
         o=0;c=0;y=0;max=0;
         for(int i=0;i<n;i++)
         {
         x=Integer.parseInt(s[i]);
         a[x]++;
         if(x>max)
         max=x;
         if(x==1)
         {
         o++;
         y+=(o-a[x]-a[x+2]);
         }
         else if(x%2==0)
         {
         c++;
         y+=(c-a[x]-a[x+2]-a[x-2]);
         }
         else
         {
         o++;
         y+=(o-a[x]-a[x+2]-a[x-2]);
         }
         }
        
         for(int i=2;i<max;i+=4)
         y+=a[i]*a[i+2]+a[i+1]*a[i+3];
         System.out.println(y);
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments