Skip to content

3094. Guess the Number Using Bitwise Questions II

Approach 1: Precalculate

  • Time: $O(30) = O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition of commonBits API.
 * int commonBits(int num);
 */

class Solution {
 public:
  int findNumber() {
    constexpr int kMaxBit = 30;
    const int sameCount = commonBits(0);
    int ans = 0;

    for (int i = 0; i <= kMaxBit; ++i) {
      if (commonBits(1 << i) > sameCount)
        ans |= 1 << i;
      commonBits(1 << i);  // Revert the XOR.
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Definition of commonBits API (defined in the parent class Problem).
 * int commonBits(int num);
 */

public class Solution extends Problem {
  public int findNumber() {
    final int kMaxBit = 30;
    final int sameCount = commonBits(0);
    int ans = 0;

    for (int i = 0; i <= kMaxBit; ++i) {
      if (commonBits(1 << i) > sameCount)
        ans |= 1 << i;
      commonBits(1 << i); // Revert the XOR.
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Definition of commonBits API.
# def commonBits(num: int) -> int:

class Solution:
  def findNumber(self) -> int:
    ans = 0
    sameCount = commonBits(0)

    for i in range(31):
      if commonBits(1 << i) > sameCount:
        ans |= 1 << i
      commonBits(1 << i)  # Revert the XOR.

    return ans

Approach 2: Compare bit by bit

  • Time: $O(30) = O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * Definition of commonBits API.
 * int commonBits(int num);
 */

class Solution {
 public:
  int findNumber() {
    constexpr int kMaxBit = 30;
    int ans = 0;

    for (int i = 0; i <= kMaxBit; ++i)
      if (commonBits(1 << i) > commonBits(1 << i))
        ans |= 1 << i;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
/**
 * Definition of commonBits API (defined in the parent class Problem).
 * int commonBits(int num);
 */

public class Solution extends Problem {
  public int findNumber() {
    final int kMaxBit = 30;
    int ans = 0;

    for (int i = 0; i <= kMaxBit; ++i)
      if (commonBits(1 << i) > commonBits(1 << i))
        ans |= 1 << i;

    return ans;
  }
}

1
2
3
4
5
6
7
8
# Definition of commonBits API.
# def commonBits(num: int) -> int:

class Solution:
  def findNumber(self) -> int:
    return functools.reduce(lambda x, i: x | (1 << i)
                            if commonBits(1 << i) > commonBits(1 << i)
                            else x, range(31), 0)