Find the Number Using Bitwise Questions I

Given a task to find a number n. There is a pre-defined API int commonSetBits(int val) that returns the number of bits where both n and val have a value of 1 in the corresponding position of their binary representation. In other words, it returns the number of set bits in the bitwise AND (&) operation of n and val. The task is to return the number n.

Example:

Input: n = 31
Output: 31
Explanation: It can be proven that it's possible to find 31 using the provided API.

Input: n = 33
Output: 33
Explanation: It can be proven that it's possible to find 33 using the provided API.

Approach:

To find the bits of a hidden number using the magic function with binary numbers that have only one 1 in them, we can follow this approach:

Get the binary numbers by performing a left shift operation on 1 and adding the numbers as: ∑ for n = 0 to n = 30 (2^n * (1 * bitPresentOrNot)

Steps-by-step approach:

• findNumber Function:
  • This function calculates the number by iterating through the first 31 bits (from 0 to 30).
  • For each bit position i, it checks if commonSetBits(1 << i) is non-zero.
  • If the condition is true, it adds 1 << i (which is equivalent to 2^i) to val.

Below is the implementation of the above approach:

#include <bits/stdc++.h> using namespace std; // Assuming `Problem` class is defined somewhere with the // function `commonSetBits` For the purpose of this example, // let's define a dummy `Problem` class with // `commonSetBits`. // Dummy implementation of commonSetBits function int commonSetBits(int n) {  // Replace this with the actual logic of commonSetBits  return n & 1; // For demonstration, let's assume it  // returns 1 for odd numbers } int findNumber() {  int num = 0;  // Loop through the first 31 bits  for (int i = 0; i <= 30; i++) {  // Check if the common set bits of (1 << i) is not  // zero  if (commonSetBits(1 << i) != 0) {  // Add the value of (1 << i) to num  num += 1 << i;  }  }  return num; } // Driver code int main() {  int result = findNumber();  cout << "The result is: " << result << endl;  return 0; } 

public class Main {  // Dummy implementation of commonSetBits function  static int commonSetBits(int n) {  // Replace this with the actual logic of commonSetBits  return n & 1; // For demonstration, let's assume it  // returns 1 for odd numbers  }  static int findNumber() {  int num = 0;  // Loop through the first 31 bits  for (int i = 0; i <= 30; i++) {  // Check if the common set bits of (1 << i) is not zero  if (commonSetBits(1 << i) != 0) {  // Add the value of (1 << i) to num  num += 1 << i;  }  }  return num;  }  // Driver code  public static void main(String[] args) {  int result = findNumber();  System.out.println("The result is: " + result);  } } // This code is contributed by Shivam 

// Dummy implementation of commonSetBits function function commonSetBits(n) {  // Replace this with the actual logic of commonSetBits  return n & 1; // For demonstration, let's assume it returns 1 for odd numbers } function findNumber() {  let num = 0;  // Loop through the first 31 bits  for (let i = 0; i <= 30; i++) {  // Check if the common set bits of (1 << i) is not zero  if (commonSetBits(1 << i) !== 0) {  // Add the value of (1 << i) to num  num += 1 << i;  }  }  return num; } // Driver code let result = findNumber(); console.log("The result is: " + result); // This code is contributed by Rambabu 

The result is: 1 

Time Complexity: O(1)
Auxiliary Space: O(1)