Last Updated: 7 Dec, 2020
Check N numbers
Moderate
Asked in companies
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.
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
Approaches
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.