Equal number of 0’s and 1’s

Given two numbers a and b. Find the minimum number of steps required to make the number of the set (1) and unset(0) bits equal in a, b, and a ^ b where you can perform the following operations:

• convert a = a ^ p, p is some number
• convert b = b ^ q, q is some number

Examples:

Input: a = 10, b = 12
output: 0
Explanation:

• in a, number of bits containing 0 = 2 and number of bits containing 1 = 2
• in b, number of bits containing 0 = 2 and number of bits containing 1 = 2

x = a ^ b = 0110, So no conversion is needed clearly, no p, q is needed. Therefore, the minimum number of steps is 0

Input : a = 0, b = 1
Output: 1
Explanation : take p = 1010, q = 1011 then we will get desired numbers a =  a ^ p and b by b  = b ^ q. So, one conversion is needed, hence the minimum number of steps here is 1

Approach: This can be solved with the following idea:

If the number of bits with 0 in a that of 1 in a, b, and x then a minimum number of steps is 0, so no conversion is needed. In all other cases, observe that if we can convert a to 1010 and b to 1100 or any kind of this where a, b, a ^ b  will follow the property mentioned in the question, then we are done as we got a = 1010, b = 1100. Clearly, the minimum number of steps will be 1 here.

Steps involved in the implementation of code:

• Calculate the total number of bits to be considered.
• Calculate the number of set bits in a, b, and a ^ b.
• After that calculate unset bits in a, b, and a ^ b.
• Check it all of them are equal to 3 of them.
  • If equal, print 0.
  • If not, print -1. 

Below is the implementation for the above approach:

Time complexity: O(log(n))
Auxilairy Space: O(1)

Given two numbers a and b. Find the minimum number of steps required to make the number of the set (1) and unset(0) bits equal in a, b, and a ^ b where you can perform the following operations:

• convert a = a ^ p, p is some number
• convert b = b ^ q, q is some number

Examples:

Input: a = 10, b = 12
output: 0
Explanation:

• in a, number of bits containing 0 = 2 and number of bits containing 1 = 2
• in b, number of bits containing 0 = 2 and number of bits containing 1 = 2

x = a ^ b = 0110, So no conversion is needed clearly, no p, q is needed. Therefore, the minimum number of steps is 0

Input : a = 0, b = 1
Output: 1
Explanation : take p = 1010, q = 1011 then we will get desired numbers a =  a ^ p and b by b  = b ^ q. So, one conversion is needed, hence the minimum number of steps here is 1

Approach: This can be solved with the following idea:

If the number of bits with 0 in a that of 1 in a, b, and x then a minimum number of steps is 0, so no conversion is needed. In all other cases, observe that if we can convert a to 1010 and b to 1100 or any kind of this where a, b, a ^ b  will follow the property mentioned in the question, then we are done as we got a = 1010, b = 1100. Clearly, the minimum number of steps will be 1 here.

Steps involved in the implementation of code:

• Calculate the total number of bits to be considered.
• Calculate the number of set bits in a, b, and a ^ b.
• After that calculate unset bits in a, b, and a ^ b.
• Check it all of them are equal to 3 of them.
  • If equal, print 0.
  • If not, print -1. 

Below is the implementation for the above approach:

Time complexity: O(log(n))
Auxilairy Space: O(1)