Question: Hexaware | 18th October | Online Assessments | XOR-AND Inversions
3
Entering edit mode

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>

1.11.2

4
Entering edit mode

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.

ADD COMMENTlink 21 months ago Shikhar Mehrotra 480

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts