6 weeks ago

John 930

Hyderabad

Question 1

XOR-AND Inversions

Problem Statement

You are given an integer array A of size N. Your task is to count and print the number of XOR-AND inversions in array A. A pair (‘i’, ‘j’) is said to be an XOR-AND inversion if and only if it satisfies the following conditions:

• 1 ≤ i < j ≤ N
• A[i]&A[j] ≥ A[i]^A[j]

Note

• Here ‘ & ’ denotes bitwise ‘AND’ , ‘ ^ ’ denotes bitwise ‘XOR’.

Input Format:

The input consists of two lines:

• The first line contains an integer N.
• The second line contains N space-separated integers denoting the array elements. 

Input will be read from the STDIN by the candidate

Output Format:

Print the count of XOR-AND inversions. 

Output will be matched to the candidate’s output printed on the STDOUT

Constraints:

• 1 ≤ N,A[i] ≤ 10^5

Example:

Input:

5

7 12 16 10 6

Output:

2

Explanation:

There are only two pairs that satisfies both the conditions those are

• (1, 5) its respective element are (7, 6) , (7&6) = 6 , (7^6) = 1, Here (7&6) >= (7^6).
• (2, 4) its respective elements are (12, 10) , (12&10) = 8, (12^10) = 6, Here (12&10) >= (12^10).

Hence the output is 2.

Sample input

6

2 4 32 8 16 64

Sample Output

0

Instructions: 

• Program should take input from standard input and print output to standard output.
• Your code is judged by an automated system, do not write any additional welcome/greeting messages
• "Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
• Additional score will be given for writing optimized code both in terms of memory and execution time

<problem>115</problem>

12 months ago

Shikhar Mehrotra 480

Chennai

Q1)
Given : A[i]&A[j]>=A[i]^A[j] and let's check for the most significant bit of A[i] and A[j] let it be at xth and yth position from right respectively.
If x is not equal to y then XOR will be always greater than AND .
If x is equal to y then AND will be greater because XOR's corresponding bit would be unset, which means same number of set bits.
Hence we need to just count pairs with same count of bits.