Oniwa and Amix Numbers

Moderate

0/80

Average time to solve is 30m

0 upvote

Asked in company

Problem statement

Nandy, Oniwa and Amix were having three integers ‘A’ ,’B’ ,’C’ .They want to a minimum number of Flip operation required in either ‘A’ or ‘B’ to make ‘A’ or ‘B’ == ‘C’ where ‘or’ is bitwise OR operation. The flip operation consists of changing a bit from 1 to 0 or from 0 to 1.

Nandy, Oniwa and Amix have to attend the meet of elite coders. So please find the minimum number of flips required to in A or B to make A or B equal to C.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. 

The first and only line of the test case consists of three integers ‘A’, ‘B’, and ‘C’.

Output Format:

For each test case, print a single line containing a single integer denoting the minimum number of flips required.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 11
1 <= A <= 10 ^ 9
1 <= B <= 10 ^ 9
1 <= C <= 10 ^ 9

Where 'T' is the number of test cases and 'A', 'B', 'C' are given integers.

Time Limit: 1 sec.

Sample Input 1:

2
2 4 5
4 2 6

Sample Output 1:

2
0

Sample Explanation:

For the first test case:-
One of the possible flip operations are :-
The binary representation of 2 is 10.
Convert 10 to 01. 2 flip operations are used .
The binary representation of 4 is 100.
The or of (100 or 01) is 101.
Thus 2 flip operations are used.

For the second test case:-
The binary representation of 2 is 10.
The binary representation of 4 is 100.
The or of (10) or (100) is 110.
Thus 0 flip operations are required.

Sample Input 2:

2
14 2 0
15 6 12

Sample Output 2:

4
3

Hint 1

Traverse the bits of C.

Approaches (1)

Approach 1

Bitwise Approach

Run a loop from 0 to 32 since there are 32 bits in int . If the ith bit of C is 1 then at least ith bit of A or B should be 1. If none of the ith bit of A and B is 1 then set the bit of either A or B to 1.Thus one flip operation is required. If the ith bit of C is 0 then the ith bit of both A and B should be 0.

Algorithm:

Run a loop from i equal 0 to 32.
Create a variable ans with default value 0.
If the ith bit of C is 1.Then check if ith of either A or B is one move to the next bit.Else set any of the ith bit of A or B to 1 and increase the ans by 1.
If the ith bit of C is 0 then the ith bit in both A and B should be 0. If the ith bit in A is 1 increase the ans by 1. Similarly, if the ith bit in B is 1 increase the ans by 1.
Return the ans.

Time Complexity

O(1) .

We are using the constant time to solve this.

Space Complexity

O(1) .

We are using constant space to solve this.

(100% EXP penalty)

Oniwa and Amix Numbers

Console