DEV Community

Dev Cookies
Dev Cookies

Posted on

🚀 Day 15: Bit Manipulation Pattern (Amazon Interview Series)

Amazon loves to test whether you can use bits for optimization instead of relying on brute force or extra memory.
This pattern helps in space-efficient, fast solutions to problems involving:

  • Unique numbers
  • Parity checks
  • Power-of-two checks
  • Subset generation

🔑 What is Bit Manipulation?

Bit manipulation means solving problems using binary representation and operators like:

  • & (AND)
  • | (OR)
  • ^ (XOR)
  • ~ (NOT)
  • << (left shift)
  • >> (right shift)

👉 Why Amazon asks this:

  • Very efficient (O(1) per operation).
  • Saves memory (no extra DS needed).
  • Trains you to think at a low level.

📝 Problem 1: Single Number

👉 Amazon-style phrasing:
Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Java Solution 

public class SingleNumber {
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int n : nums) {
            result ^= n; // XOR cancels out duplicates
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4,1,2,1,2};
        System.out.println(singleNumber(nums)); // Output: 4
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
✅ Amazon relevance: Detect unique product ID among duplicates.

📝 Problem 2: Missing Number

👉 Amazon-style phrasing:
Given an array containing n distinct numbers in the range [0, n], find the missing one.

Java Solution 

public class MissingNumber {
    public static int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i]; // XOR index with value
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {3,0,1};
        System.out.println(missingNumber(nums)); // Output: 2
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(n)
✅ Why Amazon likes it: Efficient inventory/ID gap detection.

📝 Problem 3: Power of Two

👉 Amazon-style phrasing:
Given an integer n, return true if it is a power of two.

Java Solution 

public class PowerOfTwo {
    public static boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }

    public static void main(String[] args) {
        System.out.println(isPowerOfTwo(16)); // true
        System.out.println(isPowerOfTwo(18)); // false
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(1)
✅ Trick: A power of two has only one set bit in binary.

📝 Problem 4: Counting Bits

👉 Amazon-style phrasing:
Given an integer n, return an array ans where ans[i] is the number of 1s in the binary representation of i.

Java Solution 

import java.util.*;

public class CountingBits {
    public static int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(countBits(5))); 
        // [0,1,1,2,1,2]
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(n)
✅ Why Amazon likes it: Used in compression, networking, and permissions systems.

📝 Problem 5: Subsets Using Bits

👉 Amazon-style phrasing:
Generate all possible subsets (the power set) of an array of unique integers.

Java Solution 

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        int total = 1 << n; // 2^n subsets

        for (int mask = 0; mask < total; mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            result.add(subset);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1,2,3};
        System.out.println(subsets(nums));
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(2^n * n)
✅ Why Amazon likes it: Feature toggles, A/B test combinations, configuration systems.

🎯 Key Takeaways

  • XOR is the weapon of choice → cancels duplicates, helps find unique/missing numbers.
  • Power of Two trick: (n & (n-1)) == 0.
  • Subset generation: Use bits instead of recursion.
  • Amazon focus: Detect anomalies, optimize space, generate configurations.

📅 Next in the series (Day 16):
👉 Matrix Traversal Pattern – solving problems like Rotate Matrix, Spiral Traversal, Set Matrix Zeroes, and pathfinding inside grids.

Top comments (0)