Check N numbers

Moderate
0/80
Average time to solve is 10m
16 upvotes
Asked in companies
UberLinkedIn

Problem statement

Given an array ‘arr’ of ‘N’ integers, make a number from those set of all integers from the ‘arr’ such that if number of ‘ith’ set bits are greater than the number of ‘ith’ unset bits then make that ‘ith’ bit of the new number as set bi otherwise make that ‘ith’ bit as unset bit.

For Example:

There are three numbers, say 8, 5 and 10. 
8 can be written as      1 0 0 0 .
5 can be written as      0 1 0 1.
10 can be written as     1 0 1 0. 
positions of the bits as i j k l.
So we can see majority bit at ith position are set bits so ith bit will be 1. Similarly for positions of j, k and l are set as 0 0 0 respectively.
So the number generated is 1 0 0 0 i.e. 8.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ representing the number of test cases.    

Then ‘T’ test cases follows:

First line of each test case contains an integer ‘N’ representing the size of the input array ‘arr’. 

Next line contains ‘N’ space separated integers denoting the elements in the ‘arr’.

Output format :

Output of each test case an integer as per the condition.

Constraints:

1 <= T <= 5
1 <= N <= 10 ^ 3
1 <= arr[i] <= 5 * (10 ^ 3)

Time Limit: 1sec
Sample Input 1:
2
3
8 4 2
3
8 8 2
Sample Output 1:
0
8
Explanation for Sample Test Case 1:
Test Case 1 :
Numbers can be represented in bits as:
1 0 0 0
0 1 0 0
0 0 1 0
i j k l
Number of set bits for ith index is 1. Number of unset bits for ith index is 2. Therefore the number of unset bits for ith index is greater than the number of set bits for ith index. So ith bit for the number will be 0.

Similarly for jth, kth and lth bit will be 0. As the number of unset bits is greater than the number of set bits. Answer will be 0 0 0 0 which represents number 0.

Test Case 2:
Numbers can be represented in bits as
1 0 0 0
1 0 0 0
0 0 1 0
i j k l

Number of set bits for ith index is 2. Number of unset bits for ith index is 1. Therefore the number of set bits for ith index is greater than the number of unset bits for ith index. So ith bit for the number will be 1.

Similarly for jth, kth and lth bit will be 0. As the number of unset bits is greater than the number of set bits. Answer will be 1 0 0 0 which represents the number 8.
Sample Input 2:
2
5
1 2 3 4 5
4
6 7 8 9
Sample Output 2:
1
0
Hint

Try thinking of counting the set bits and unset bits for every integer in the array.

Approaches (1)
Bitwise Operations

The idea is to count the number of set and unset bits for every integer of ‘arr’ and for every ‘ith’ index of all positions in the maximum bit.

 

Approach :

  • First declare variables ‘count0’ to store the count of unset bits, ‘count1’ to store the count of set bits, ‘maxBits’ to store the maximum number of bits among all elements of array, ‘ans’ to store the answer, ‘maxNum’ to store the maximum number among all elements of ‘arr’, ‘k’ to 0.
  • First find the maximum element among all the elements of ‘arr’ and store the maximum element in ‘maxNum’.
  • Now count the bits in ‘maxNum’ and store the count in ‘maxBits’.
  • Iterate till ‘maxBits’  greater than 0.
  • Initialize ‘count0’ and ‘count1’ with 0.
  • Iterate throughout the ‘arr’ with the iterator pointer ‘i’:
    • Check if the current bit is set then increment ‘count1’.
    • Else increment ‘count0’.
    • Now right shift the bit by 1.
  • Now check if ‘count1’ is greater than ‘count0’ then make ans as ans + (1 << k).
  • Increment ‘k’.
  • Return ‘ans’ to the function.
Time Complexity

O(N), where ‘N’ denotes the size of the input array.
 

As, we are traversing over the input array once. Therefore, overall time complexity will be O(N).

Space Complexity

O(1)

 

As constant space is used. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Check N numbers
Full screen
Console