Last Updated: 24 Feb, 2021
Minimum And Maximum
Easy
Asked in companies
You have been given two integers 'A' and 'B' return minimum and maximum of both the numbers without branching.
Note :
Branching includes if-else statements, the ternary operator, or switch-case statements. Therefore you should not use any of the above approaches to solving the problem.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The only line of each test case contains two space-separated integers 'A' and 'B' representing two integers whose minimum and the maximum you need to return.
Output Format :
For each test case return the minimum and maximum of two numbers.
Note:
You do not need to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 1000
1 <= 'A' <= 10^9
1 <= 'B' <= 10^9
Time Limit: 1sec
Approaches
Let us assume ‘b’ is minimum and ‘a’ is maximum among ‘a’ and ‘b’.( ‘a’ < ‘b’ ) is the comparison we will be using. We will calculate minimum and maximum as follows:
- We can write the minimum as ‘b’ ^ (( ‘a’ ^ ‘b’) & - ( ‘a’ < ‘b’)).
- If ‘b’ is minimum ‘a’ < ‘b’ comes out to be all zeroes. (‘a’ ^ ‘b’) & ‘0’ comes out to ‘0’. Therefore expression value comes out to be ‘b’ finally which is the minimum.
- If ‘a’ is minimum ‘a’ < ‘b’ comes out to be all ones. (‘a’ ^ ‘b’) & ‘1’ comes out to (‘a’ ^ ‘b’). Therefore expression value comes out to be ‘a’ finally which is the minimum.
- We can write maximum as ‘a’ ^ (( ‘a’ ^ ‘b’) & - ( ‘a’ < ‘b’)).
- If ‘a’ is maximum ‘a’ < ‘b’ comes out to be all zeroes. (‘a’ ^ ‘b’) & ‘0’ comes out to ‘0’. Therefore expression value comes out to be ‘a’ finally which is the maximum.
- If ‘b’ is maximum ‘a’ < ‘b’ comes out to be all ones. (‘a’ ^ ‘b’) & ‘1’ comes out to (‘a’ ^ ‘b’). Therefore expression value comes out to be ‘b’ finally which is the maximum.
- Return the minimum and the maximum.
Let us assume ‘b’ is minimum and ‘a’ is maximum among ‘a’ and ‘b’.( ‘a’ - ‘b’ ) is non-negative if our assumption is true otherwise negative. We will calculate minimum and maximum as follows:
- We can write the minimum as ‘b’ + ((‘a’ - ‘b’) & ((‘a’ - ‘b’) >> (noOfBitsInInt - 1))). On right shifting ‘a’ - ‘b’ by 1 less than no of bits in int we get the most significant bit.
- If ‘b’ is minimum ‘a’ - ‘b’ comes out to be non-negative and on right shifting, we get ‘0’. (‘a’ - ‘b’) & ‘0’ comes out to ‘0’. Therefore expression value comes out to be ‘b’ finally which is the minimum.
- If ‘a’ is minimum ‘a’ - ‘b’ comes out to be negative and on right shifting, we get ‘1’. (‘a’ - ‘b’) & ‘1’ comes out to (‘a’ - ‘b’). Therefore expression value comes out to be ‘a’ finally which is the minimum.
- We can write maximum as ‘a’ - ((‘a’ - ‘b’) & ((‘a’ - ‘b’) >> (noOfBitsInInt - 1))). On right shifting ‘a’ - ‘b’ by 1 less than no of bits in int we get most significant bit.
- If ‘a’ is maximum ‘a’ - ‘b’ comes out to be non-negative and on right shifting, we get ‘0’. (‘a’ - ‘b’) & ‘0’ comes out to ‘0’. Therefore expression value comes out to be ‘a’ finally which is the maximum.
- If ‘b’ is maximum ‘a’ - ‘b’ comes out to be negative and on right shifting, we get ‘1’. (‘a’ - ‘b’) & ‘1’ comes out to (‘a’ - ‘b’). Therefore expression value comes out to be ‘b’ finally which is the maximum.
- Return the minimum and the maximum.