Interview ✔

1. Minimum Bit Flips to Convert Number

   1. 13 March, 2026: 00.05.47 ✔
   2. 19 March, 2026: 00.2.16 ✔ 😵‍💫
      • Try to solve within O(1) time and space complexity

2. Single Number - I

3. Power Set Bit Manipulation

   1. 13 March, 2026: 00.12.09 ✔
   2. 19 March, 2026: 00.5.49 ✔ 😵‍💫

4. XOR of numbers in a given range

   1. 13 March, 2026: 00.00.00 ❌
      • Failed at optimization
   2. 19 March, 2026: 00.5.49 ✔

5. Single Number - II

   1. 14 March, 2026: 00.00.00 ❌
      • Failed at optimization
   2. 19 March, 2026: 00.00.00 ❌
      • Failed at implementation

   Bruteforce

   • If every number appears 3 times, then for each bit position (0–31):
   • The sum of bits from all numbers will be a multiple of 3
   • Except the bits belonging to the single number

   int singleNumber(vector<int>& nums) {
    int result = 0;
   
    for(int i = 0; i < 32; i++) {
        int count = 0;
   
        for(int num : nums) {
            if(num & (1 << i)) {
                count++;
            }
        }
   
        if(count % 3) {
            result |= (1 << i);
        }
    }
   
    return result;
   }

   • Time: O(32 × n) ≈ O(n)
   • Space: O(1)

   Optimization

   We keep two variables:

   ones → bits that appeared 1 time
   twos → bits that appeared 2 times

   When a bit appears third time, we remove it from both.

   int singleNumber(vector<int>& nums) {
       int ones = 0, twos = 0;
   
       for (int num : nums) {
           ones = (ones ^ num) & ~twos;
           twos = (twos ^ num) & ~ones;
       }
   
       return ones;
   }

   What Each Operation Means

   XOR (^)

   • toggles bits
   • adds a number to the set if it wasn't there
   • removes if it was there

   So:

   ones ^ num

   means toggle bits of num in ones

   AND NOT (& ~)

   This removes bits.

   ones & ~twos

   means ➡ remove bits that already moved to twos

   State Transition

   For each bit we simulate this cycle:

   0 occurrences  → ones
   ones           → twos
   twos           → removed

   So counts go:

   00 → 01 → 10 → 00

   Dry Run Example

   Input:

   [2,2,3,2]

   Binary:

   2 = 10
   3 = 11

   Start:

   ones = 00
   twos = 00

   Step 1: num = 2 (10)

   ones = (00 ^ 10) & ~00
        = 10
   
   twos = (00 ^ 10) & ~10
        = 00

   State:

   ones = 10
   twos = 00

   Step 2: num = 2 (10)

   ones = (10 ^ 10) & ~00
        = 00
   
   twos = (00 ^ 10) & ~00
        = 10

   State:

   ones = 00
   twos = 10

   Step 3: num = 3 (11)

   ones = (00 ^ 11) & ~10
        = 01
   
   twos = (10 ^ 11) & ~01
        = 00

   State:

   ones = 01
   twos = 00

   Step 4: num = 2 (10)

   ones = (01 ^ 10) & ~00
        = 11
   
   twos = (00 ^ 10) & ~11
        = 00

   Final:

   ones = 11

   Binary 11 = 3

   Why It Works

   Each bit independently follows this finite-state machine:

   count = 0 → ones
   count = 1 → twos
   count = 2 → reset

   So after processing the array:

   • bits appearing 3 times disappear
   • bits appearing once remain in ones

   Complexity

   Metric	Value
   Time	O(n)
   Space	O(1)

• https://leetcode.com/problems/single-number-iii/
  1. 19 March, 2026: 00.00.00 ❌
     • Failed at optimization
  • The xor of same number return 0
  • The xor of two unique number return where its bits differ
  • we will seperate the numbers in two group, based on the rightmost set bit of (xor = a ^ b)
    • Group 1: numbers where this bit is set (1)
    • Group 2: numbers where this bit is not set (0)
  • Duplicates will always go into the same group and cancel out after XOR
  • The two unique numbers will fall into different groups, so XOR in each group gives the answer