Maximize Bitwise AND product function

Given two non-negative integers A and B find the smallest non-negative integer m such that the product of (A & m) and (B & m) is maximized.

Examples:

Input: A = 5, B = 10
Output: 15
Explanation: By taking m = 15 we got the maximum value of 50. We can also get 50 by other integers but 15 is the smallest to give maximum value.

Input: A = 10000000, B = 64235678983
Output: 64235683719

Naive Approach: To solve the problem follow the below idea:

We can iterate through all the possible numbers from 0 to 2 times the maximum of A and B and store the maximum value. For each maximum value update the value of m and return the answer.

Below is the code for the above approach:

Time Complexity: 
Auxiliary Space: 

Efficient Approach: To solve the problem follow the below observations:

The observation is that the integers can be large, bitwise manipulation should have some play in solving this problem. To maximize the product of two numbers we should make the two numbers as large as possible. AND of two numbers is largest when two numbers are the same i.e. the set bit locations are the same. We find m such that the set bits of both A and B are set. Logical OR sets the bit ON when both or any one of the bits is SET. Hence A OR B will give us the value of m. It will automatically be the minimum value as only these bits are set which are contributing to the answer. Using this approach we can solve the problem of large integers and also reduce the complexity to constant time.

Below are the steps for the above approach:

• Initialize two variables m = 0 that will store the smallest integer value such that the product of (A & m) and (B & m) is maximized.
• Perform logical OR operation on A and B and store the result in variable m.
• Return m.

Below is the code for the above approach:

Time Complexity: 
Auxiliary Space: 

Given two non-negative integers A and B find the smallest non-negative integer m such that the product of (A & m) and (B & m) is maximized.

Examples:

Input: A = 5, B = 10
Output: 15
Explanation: By taking m = 15 we got the maximum value of 50. We can also get 50 by other integers but 15 is the smallest to give maximum value.

Input: A = 10000000, B = 64235678983
Output: 64235683719

Naive Approach: To solve the problem follow the below idea:

We can iterate through all the possible numbers from 0 to 2 times the maximum of A and B and store the maximum value. For each maximum value update the value of m and return the answer.

Below is the code for the above approach:

Time Complexity: 
Auxiliary Space: 

Efficient Approach: To solve the problem follow the below observations:

The observation is that the integers can be large, bitwise manipulation should have some play in solving this problem. To maximize the product of two numbers we should make the two numbers as large as possible. AND of two numbers is largest when two numbers are the same i.e. the set bit locations are the same. We find m such that the set bits of both A and B are set. Logical OR sets the bit ON when both or any one of the bits is SET. Hence A OR B will give us the value of m. It will automatically be the minimum value as only these bits are set which are contributing to the answer. Using this approach we can solve the problem of large integers and also reduce the complexity to constant time.

Below are the steps for the above approach:

• Initialize two variables m = 0 that will store the smallest integer value such that the product of (A & m) and (B & m) is maximized.
• Perform logical OR operation on A and B and store the result in variable m.
• Return m.

Below is the code for the above approach:

Time Complexity: 
Auxiliary Space: