Bit Manipulation || NETCORE OA
Anonymous User
567
Interview

You are given an array nums consisting of N integers where N is even.

You have to perform the following operation N/2 times:

  1. Select nums i, nums j from the list
  2. Take their bitwise OR, add the value of the least significant set bit to the score
  3. Delete those two numbers

If the selected numbers are 5=(101)2 and 7=(111)2 then the bitwise OR of the two numbers is 7=(111)2. So, the least significant bit of 7 i.e. 1=(001)2 will be added to the current score.

Notes

  • 1-based indexing is followed
  • A bitwise OR is a binary operation that takes two bit patterns of equal length and performs the logical inclusive OR operation on each pair of corresponding bits. The result in each position is 0 if both bits are 0, while otherwise, the result is 1.
  • Strings in ()2 denote the binary representation.

Task

Print the maximum possible score.

Example

Assumptions

  • N=4
  • nums = [1,2,1,4]

Approach

  • For the given case pairing (1, 1), (2, 4) that is (nums[1], nums[3]), (nums[2], nums[4]) with 1-based indexing results in a maximum score of 3, pairing like (4, 1),(1, 2) that is (nums[4], nums[1]), (nums[3], nums[2]) results in 2.

Hence, the answer is 3.

Function description

Complete the MaxPairs function provided in the editor. The function takes the following 2 parameters and returns the maximum possible score based on the parameters.

  • N: Represents an integer denoting the total number of integers
  • nums: Represents an array containing N integers

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

  • The first line contains T denoting the number of test cases. T also specifies the number of times you have to run the MaxPairs function on a different set of inputs
  • For each test case:
    • The first line contains N denoting the number of integers.
    • The second line contains N space-separated integers denoting the elements of array nums.

Output format
For each test case, print the answer representing the maximum possible score in a new line.

Constraints

1<= T<= 1000 2<=N<=2*10^5, N is even 1<=nums i <= 10^9

The sum of N does ot exceed 2*10^5

Sample Input

1
6
9 4 10 4 5 7

Output :
6

Comments (0)