Gray Code

🎯

Gray Code

mediumBIT_MANIPULATIONAmazonGoogleBloomberg

Imagine you need to design a sequence of binary codes for a rotary encoder where only one bit changes at a time to minimize errors during transitions.

💡 This problem involves generating a sequence of binary numbers where consecutive numbers differ by only one bit. Beginners often struggle because it requires understanding bitwise operations and the concept of reflected Gray codes, which is not intuitive at first. Think of it like a sequence of light switches where only one switch changes at a time to avoid confusion.

📋

Problem Statement

Given a non-negative integer n representing the total number of bits in the code, generate a sequence of Gray codes. A Gray code sequence must begin with 0 and each successive number differs from the previous by exactly one bit. Return the sequence as a list of integers.

1 ≤ n ≤ 16

💡

Example

Input"n = 2"

Output[0, 1, 3, 2]

The 2-bit Gray code sequence starts at 0 (00), then 1 (01), then 3 (11), then 2 (10). Each adjacent pair differs by one bit.

• n = 0 → [0]
• n = 1 → [0, 1]
• n = 16 → large output but must be correct
• n = 2 → verify reflected pattern correctness

⚠️

Common Mistakes

Not checking that consecutive numbers differ by exactly one bit

Generated sequence may have invalid transitions breaking Gray code property

✅ Use XOR and power-of-two check to verify one-bit difference

Using brute force backtracking for large n

Code times out or runs extremely slowly

✅ Use recursive reflected code or direct formula instead

Incorrect bit shifting or XOR operations

Incorrect Gray codes generated

✅ Carefully implement i ^ (i >> 1) formula and test with small inputs

Not handling base case n=0 correctly

Code may crash or return empty list

✅ Explicitly return [0] when n=0

Reversing the list incorrectly in recursive approach

Sequence does not maintain one-bit difference

✅ Reverse the previous list exactly before prefixing the leading 1 bit

🧠

Brute Force (Backtracking with Bit Difference Check)

💡 This approach exists to build intuition by explicitly generating all permutations and checking the one-bit difference condition, helping beginners understand the problem's constraints and why naive generation is inefficient. Imagine trying every possible path in a maze to find the correct sequence.

Intuition

Generate all possible n-bit numbers and try to build a sequence by choosing numbers that differ by exactly one bit from the last number in the sequence, backtracking if stuck.

Algorithm

1. Generate all numbers from 0 to 2^n - 1.
2. Start with 0 in the sequence.
3. At each step, try to add a number not used yet that differs by exactly one bit from the last number.
4. Backtrack if no such number can be found until the sequence is complete.

💡 This algorithm is hard to see at first because it involves recursive backtracking and bitwise difference checks, which can be confusing without a clear mental model.

</>

Code

def grayCode(n):
    def differ_by_one_bit(x, y):
        xor = x ^ y
        return xor != 0 and (xor & (xor - 1)) == 0

    def backtrack(path, used):
        if len(path) == (1 << n):
            return True
        last = path[-1]
        for num in range(1, 1 << n):  # start from 1 to avoid re-adding 0
            if not used[num] and differ_by_one_bit(last, num):
                used[num] = True
                path.append(num)
                if backtrack(path, used):
                    return True
                path.pop()
                used[num] = False
        return False

    path = [0]
    used = [False] * (1 << n)
    used[0] = True
    backtrack(path, used)
    return path

# Driver code
if __name__ == '__main__':
    print(grayCode(2))

Line Notes

def differ_by_one_bit(x, y):Defines a helper to check if two numbers differ by exactly one bit

xor = x ^ yXOR highlights bits that differ between x and y

return xor != 0 and (xor & (xor - 1)) == 0Checks if XOR is a power of two, meaning exactly one bit differs

def backtrack(path, used):Recursive function to build Gray code sequence

if len(path) == (1 << n):Base case: sequence complete when length is 2^n

last = path[-1]Get last number in current sequence to compare

for num in range(1, 1 << n):Try all possible numbers for next step, starting from 1 to avoid re-adding 0

if not used[num] and differ_by_one_bit(last, num):Choose unused number differing by one bit

used[num] = TrueMark number as used to avoid repeats

path.append(num)Add number to current sequence

if backtrack(path, used):Recurse to continue building sequence

path.pop()Backtrack by removing last number if dead end

used[num] = FalseUnmark number when backtracking

path = [0]Initialize sequence with 0 as required

used = [False] * (1 << n)Track which numbers have been used

used[0] = TrueMark 0 as used initially

backtrack(path, used)Start backtracking search

return pathReturn the completed Gray code sequence

import java.util.*;
public class GrayCodeBrute {
    public static boolean differByOneBit(int x, int y) {
        int xor = x ^ y;
        return xor != 0 && (xor & (xor - 1)) == 0;
    }

    public static boolean backtrack(List<Integer> path, boolean[] used, int n) {
        if (path.size() == (1 << n)) return true;
        int last = path.get(path.size() - 1);
        for (int num = 1; num < (1 << n); num++) { // start from 1 to avoid re-adding 0
            if (!used[num] && differByOneBit(last, num)) {
                used[num] = true;
                path.add(num);
                if (backtrack(path, used, n)) return true;
                path.remove(path.size() - 1);
                used[num] = false;
            }
        }
        return false;
    }

    public static List<Integer> grayCode(int n) {
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[1 << n];
        path.add(0);
        used[0] = true;
        backtrack(path, used, n);
        return path;
    }

    public static void main(String[] args) {
        System.out.println(grayCode(2));
    }
}

Line Notes

public static boolean differByOneBit(int x, int y) {Helper to check one-bit difference using XOR

int xor = x ^ y;XOR highlights differing bits

return xor != 0 && (xor & (xor - 1)) == 0;Checks if XOR is power of two

public static boolean backtrack(List<Integer> path, boolean[] used, int n) {Recursive backtracking to build sequence

if (path.size() == (1 << n)) return true;Base case: sequence complete

int last = path.get(path.size() - 1);Get last number in sequence

for (int num = 1; num < (1 << n); num++) {Try all possible numbers starting from 1 to avoid re-adding 0

if (!used[num] && differByOneBit(last, num)) {Choose unused number differing by one bit

used[num] = true;Mark number used

path.add(num);Add number to sequence

if (backtrack(path, used, n)) return true;Recurse to continue

path.remove(path.size() - 1);Backtrack by removing last number

used[num] = false;Unmark number when backtracking

List<Integer> path = new ArrayList<>();Initialize sequence list

boolean[] used = new boolean[1 << n];Track used numbers

path.add(0);Start sequence with 0

used[0] = true;Mark 0 used

backtrack(path, used, n);Start backtracking

#include <iostream>
#include <vector>
using namespace std;

bool differByOneBit(int x, int y) {
    int xor_ = x ^ y;
    return xor_ != 0 && (xor_ & (xor_ - 1)) == 0;
}

bool backtrack(vector<int>& path, vector<bool>& used, int n) {
    if ((int)path.size() == (1 << n)) return true;
    int last = path.back();
    for (int num = 1; num < (1 << n); num++) { // start from 1 to avoid re-adding 0
        if (!used[num] && differByOneBit(last, num)) {
            used[num] = true;
            path.push_back(num);
            if (backtrack(path, used, n)) return true;
            path.pop_back();
            used[num] = false;
        }
    }
    return false;
}

vector<int> grayCode(int n) {
    vector<int> path = {0};
    vector<bool> used(1 << n, false);
    used[0] = true;
    backtrack(path, used, n);
    return path;
}

int main() {
    vector<int> res = grayCode(2);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

bool differByOneBit(int x, int y) {Helper to check one-bit difference

int xor_ = x ^ y;XOR to find differing bits

return xor_ != 0 && (xor_ & (xor_ - 1)) == 0;Check if XOR is power of two

bool backtrack(vector<int>& path, vector<bool>& used, int n) {Recursive backtracking function

if ((int)path.size() == (1 << n)) return true;Base case: full sequence generated

int last = path.back();Get last element in sequence

for (int num = 1; num < (1 << n); num++) {Try all candidates starting from 1 to avoid re-adding 0

if (!used[num] && differByOneBit(last, num)) {Choose unused number differing by one bit

used[num] = true;Mark number as used

path.push_back(num);Add number to sequence

if (backtrack(path, used, n)) return true;Recurse to continue

path.pop_back();Backtrack by removing last number

used[num] = false;Unmark number when backtracking

vector<int> path = {0};Initialize sequence with 0

vector<bool> used(1 << n, false);Track used numbers

used[0] = true;Mark 0 used

backtrack(path, used, n);Start backtracking

function grayCode(n) {
    function differByOneBit(x, y) {
        let xor = x ^ y;
        return xor !== 0 && (xor & (xor - 1)) === 0;
    }

    function backtrack(path, used) {
        if (path.length === (1 << n)) return true;
        let last = path[path.length - 1];
        for (let num = 1; num < (1 << n); num++) { // start from 1 to avoid re-adding 0
            if (!used[num] && differByOneBit(last, num)) {
                used[num] = true;
                path.push(num);
                if (backtrack(path, used)) return true;
                path.pop();
                used[num] = false;
            }
        }
        return false;
    }

    let path = [0];
    let used = new Array(1 << n).fill(false);
    used[0] = true;
    backtrack(path, used);
    return path;
}

// Test
console.log(grayCode(2));

Line Notes

function differByOneBit(x, y) {Helper to check if two numbers differ by one bit

let xor = x ^ y;XOR to find differing bits

return xor !== 0 && (xor & (xor - 1)) === 0;Check if XOR is power of two

function backtrack(path, used) {Recursive backtracking function

if (path.length === (1 << n)) return true;Base case: full sequence generated

let last = path[path.length - 1];Get last number in sequence

for (let num = 1; num < (1 << n); num++) {Try all possible numbers starting from 1 to avoid re-adding 0

if (!used[num] && differByOneBit(last, num)) {Choose unused number differing by one bit

used[num] = true;Mark number as used

path.push(num);Add number to sequence

if (backtrack(path, used)) return true;Recurse to continue

path.pop();Backtrack by removing last number

used[num] = false;Unmark number when backtracking

let path = [0];Initialize sequence with 0

let used = new Array(1 << n).fill(false);Track used numbers

used[0] = true;Mark 0 used

backtrack(path, used);Start backtracking

⏱

Complexity

TimeO((2^n)!)

SpaceO(2^n)

The brute force tries all permutations of 2^n numbers, which is factorial in size, making it infeasible for large n.

💡 For n=4, 2^4=16 numbers, factorial of 16 is huge (~2.1e13), so this approach is only practical for very small n.

Interview Verdict: TLE

This approach is too slow for large inputs but is valuable to understand the problem constraints and why optimization is needed.

🧠

Using Reflected Gray Code Construction (Recursive)

💡 This approach uses the classic reflected Gray code construction, which is a well-known method to generate Gray codes efficiently and intuitively. Imagine folding a paper with codes for n-1 bits and then adding a leading bit to create the n-bit codes, ensuring only one bit changes between consecutive codes.

Intuition

Build Gray codes for n bits by prefixing 0 to the Gray codes of n-1 bits, then prefixing 1 to the reversed Gray codes of n-1 bits.

Algorithm

1. If n is 0, return [0].
2. Recursively generate Gray codes for n-1 bits.
3. Create a new list by prefixing 0 to the n-1 bit codes.
4. Append the reversed n-1 bit codes with a leading 1 bit added.
5. Return the combined list.

💡 The recursion and reversal steps can be tricky to visualize but ensure the one-bit difference property.

</>

Code

def grayCode(n):
    if n == 0:
        return [0]
    prev = grayCode(n - 1)
    add_on = 1 << (n - 1)
    return prev + [x + add_on for x in reversed(prev)]

# Driver code
if __name__ == '__main__':
    print(grayCode(2))

Line Notes

if n == 0:Base case: Gray code for 0 bits is [0]

prev = grayCode(n - 1)Recursively get Gray code for n-1 bits

add_on = 1 << (n - 1)Calculate bit to add as prefix for second half

return prev + [x + add_on for x in reversed(prev)]Concatenate original and reversed with prefix to ensure one-bit difference

import java.util.*;
public class GrayCodeReflected {
    public static List<Integer> grayCode(int n) {
        if (n == 0) {
            return new ArrayList<>(Arrays.asList(0));
        }
        List<Integer> prev = grayCode(n - 1);
        int addOn = 1 << (n - 1);
        List<Integer> result = new ArrayList<>(prev);
        for (int i = prev.size() - 1; i >= 0; i--) {
            result.add(prev.get(i) + addOn);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(grayCode(2));
    }
}

Line Notes

if (n == 0) {Base case: Gray code for 0 bits

List<Integer> prev = grayCode(n - 1);Recursive call for n-1 bits

int addOn = 1 << (n - 1);Bit to prefix for second half

List<Integer> result = new ArrayList<>(prev);Start with first half

for (int i = prev.size() - 1; i >= 0; i--) {Append reversed second half with prefix

result.add(prev.get(i) + addOn);Add prefix bit to reversed codes

#include <iostream>
#include <vector>
using namespace std;

vector<int> grayCode(int n) {
    if (n == 0) return {0};
    vector<int> prev = grayCode(n - 1);
    int addOn = 1 << (n - 1);
    vector<int> result(prev);
    for (int i = (int)prev.size() - 1; i >= 0; i--) {
        result.push_back(prev[i] + addOn);
    }
    return result;
}

int main() {
    vector<int> res = grayCode(2);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

if (n == 0) return {0};Base case for 0 bits

vector<int> prev = grayCode(n - 1);Recursive call for n-1 bits

int addOn = 1 << (n - 1);Bit to prefix for second half

vector<int> result(prev);Copy first half

for (int i = (int)prev.size() - 1; i >= 0; i--) {Append reversed second half with prefix

result.push_back(prev[i] + addOn);Add prefix bit

function grayCode(n) {
    if (n === 0) return [0];
    let prev = grayCode(n - 1);
    let addOn = 1 << (n - 1);
    let result = prev.slice();
    for (let i = prev.length - 1; i >= 0; i--) {
        result.push(prev[i] + addOn);
    }
    return result;
}

// Test
console.log(grayCode(2));

Line Notes

if (n === 0) return [0];Base case for 0 bits

let prev = grayCode(n - 1);Recursive call for n-1 bits

let addOn = 1 << (n - 1);Bit to prefix for second half

let result = prev.slice();Copy first half

for (let i = prev.length - 1; i >= 0; i--) {Append reversed second half with prefix

result.push(prev[i] + addOn);Add prefix bit

⏱

Complexity

TimeO(2^n)

SpaceO(2^n)

Each recursive call generates the Gray code for n-1 bits and then doubles the list size by appending reversed codes with a prefix bit.

💡 For n=4, this generates 16 codes efficiently without backtracking, making it practical for interview coding.

Interview Verdict: Accepted

This approach is efficient and elegant, suitable for coding in interviews.

🧠

Optimal Bitwise Formula (Direct Computation)

💡 This approach uses a direct formula to compute the i-th Gray code without recursion or backtracking, leveraging bitwise XOR operations for optimal performance. It's like a magic shortcut that transforms the binary sequence into Gray code instantly.

Intuition

The i-th Gray code can be computed as i XOR (i shifted right by 1), which ensures only one bit changes between consecutive codes.

Algorithm

1. Initialize an empty list to hold Gray codes.
2. For each number i from 0 to 2^n - 1, compute gray = i ^ (i >> 1).
3. Append gray to the list.
4. Return the list after processing all numbers.

💡 This algorithm is straightforward once the formula is understood, avoiding recursion or complex logic.

</>

Code

def grayCode(n):
    # Generate Gray code sequence using XOR formula
    return [i ^ (i >> 1) for i in range(1 << n)]

# Driver code
if __name__ == '__main__':
    print(grayCode(2))

Line Notes

def grayCode(n):Defines the main function to generate Gray codes

# Generate Gray code sequence using XOR formulaComment explaining the formula usage

return [i ^ (i >> 1) for i in range(1 << n)]Computes Gray code for each i using XOR with right-shifted i

import java.util.*;
public class GrayCodeFormula {
    public static List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        int size = 1 << n;
        for (int i = 0; i < size; i++) {
            result.add(i ^ (i >> 1));
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(grayCode(2));
    }
}

Line Notes

List<Integer> result = new ArrayList<>();Initialize list to store Gray codes

int size = 1 << n;Calculate total number of codes

for (int i = 0; i < size; i++) {Iterate over all numbers

result.add(i ^ (i >> 1));Compute Gray code using XOR formula

#include <iostream>
#include <vector>
using namespace std;

vector<int> grayCode(int n) {
    vector<int> result;
    int size = 1 << n;
    for (int i = 0; i < size; i++) {
        result.push_back(i ^ (i >> 1));
    }
    return result;
}

int main() {
    vector<int> res = grayCode(2);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

vector<int> result;Initialize vector to store Gray codes

int size = 1 << n;Calculate total number of codes

for (int i = 0; i < size; i++) {Iterate over all numbers

result.push_back(i ^ (i >> 1));Compute Gray code using XOR formula

function grayCode(n) {
    let result = [];
    let size = 1 << n;
    for (let i = 0; i < size; i++) {
        result.push(i ^ (i >> 1));
    }
    return result;
}

// Test
console.log(grayCode(2));

Line Notes

function grayCode(n) {Defines the main function to generate Gray codes

let result = [];Initialize array to store Gray codes

let size = 1 << n;Calculate total number of codes

for (let i = 0; i < size; i++) {Iterate over all numbers

result.push(i ^ (i >> 1));Compute Gray code using XOR formula

⏱

Complexity

TimeO(2^n)

SpaceO(2^n)

We compute each Gray code in constant time using bitwise operations, iterating over 2^n numbers.

💡 For n=16, this means computing 65536 codes efficiently without recursion or backtracking.

Interview Verdict: Accepted

This is the optimal approach to implement in interviews due to its simplicity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the optimal bitwise formula approach is preferred for coding due to simplicity and efficiency. The recursive approach is good for explaining the concept. Brute force is mainly for understanding and should not be coded for large inputs.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O((2^n)!)	O(2^n)	Yes (deep recursion)	Yes	Mention only - never code
2. Recursive Reflected Gray Code	O(2^n)	O(2^n)	No (depth n)	Yes	Good to explain concept, code if asked
3. Bitwise Formula (Optimal)	O(2^n)	O(2^n)	No	N/A	Best approach to code in interview

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the recursive and optimal solutions.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force backtracking approach to demonstrate understanding of the problem.Step 3: Explain the recursive reflected Gray code construction as a more efficient method.Step 4: Present the optimal bitwise formula solution for best performance.Step 5: Code the optimal solution and test with sample inputs.

Time Allocation

Clarify: 2min → Approach explanation: 5min → Coding: 8min → Testing & discussion: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of bitwise operations, recursion, and ability to optimize from brute force to an elegant formula.

Common Follow-ups

• How to generate Gray code in reverse order → Reverse the generated list or modify formula accordingly.
• Explain why XOR with right-shifted i produces Gray code → It encodes the bit difference pattern ensuring one bit changes.

💡 These follow-ups test deeper understanding of Gray code properties and ability to manipulate bitwise formulas.

🔍

Pattern Recognition

When to Use

1) Problem asks for sequence of binary numbers with one-bit difference between consecutive elements; 2) Input size suggests exponential output; 3) Bitwise operations are hinted; 4) Gray code or reflected code keywords appear.

Signature Phrases

sequence differs by one bitGray codereflected code

NOT This Pattern When

Problems that generate all binary numbers without the one-bit difference constraint or that require counting bits rather than generating sequences.

Similar Problems

Generate Parentheses - both involve recursive construction and reflectionSubsets - similar exponential output and bitmask usagePermutations - backtracking with constraints

Practice

1. The following code attempts to find two missing numbers using XOR partitioning but sometimes returns incorrect results. Identify the bug.

medium

A. Final return statement returning [x, y]

B. Line calculating xor_all with XOR of all numbers

C. Loop partitioning numbers based on set_bit

D. Line calculating set_bit using bitwise OR instead of AND

Solution

1. Step 1: Understand set_bit calculation

   Correct approach finds rightmost set bit using xor_all & (-xor_all). Using OR instead breaks partitioning.

2. Step 2: Consequence of bug

   Incorrect set_bit causes wrong grouping of numbers, leading to incorrect missing numbers returned.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Replacing OR with AND fixes partitioning and output [OK]

Hint: Rightmost set bit must be found with AND, not OR [OK]

Common Mistakes:

• Using OR instead of AND for set bit
• Misplacing XOR operations
• Returning wrong variables

2. What is the time and space complexity of the optimal bitwise FSM solution for the Single Number II problem?

medium

A. Time: O(n), Space: O(1)

B. Time: O(n), Space: O(n)

C. Time: O(n^2), Space: O(1)

D. Time: O(n log n), Space: O(n)

Solution

1. Step 1: Identify complexity of outer and inner loops

   The algorithm iterates once over the input array (n elements), performing constant time bitwise operations per element.

2. Step 2: Check if recursion stack adds extra space

   No recursion or extra data structures are used; only fixed variables 'ones' and 'twos' consume constant space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear time and constant space confirmed by single pass and fixed variables [OK]

Hint: Bitwise FSM uses fixed variables, no extra data structures [OK]

Common Mistakes:

• Assuming sorting or hash map space/time
• Confusing bit operations cost

3. The following code attempts to find the single number in an array using XOR. Identify the line containing the subtle bug that causes incorrect results.

medium

A. Line 2: Initializing result to nums[0] instead of 0

B. Line 4: Returning result without sorting

C. Line 3: Looping over nums including the first element again

D. Line 1: Function definition

Solution

1. Step 1: Analyze initialization of result

   Result initialized to nums[0], then XORed again with nums[0] in loop, cancelling it out incorrectly.

2. Step 2: Understand correct initialization

   Result should start at 0 so XOR accumulates all elements exactly once.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Initializing to zero avoids double XOR of first element [OK]

Hint: XOR accumulator must start at zero [OK]

Common Mistakes:

• Initializing with first element causes double XOR
• Loop includes first element again
• Misplaced return statement

4. Suppose the input integer can be negative and you want to count the number of 1 bits in its 32-bit two's complement representation. Which modification ensures correct counting for all integers?

hard

A. Use logical AND with 1 and left shift the number until it becomes zero.

B. Use the naive loop with 'while n != 0' and right shift operator as is.

C. Convert the integer to its absolute value before counting bits.

D. Mask the input with 0xFFFFFFFF before counting bits to treat it as unsigned.

Solution

1. Step 1: Understand two's complement representation

   Negative numbers have sign-extended bits; masking with 0xFFFFFFFF treats them as unsigned 32-bit values.

2. Step 2: Apply mask before counting bits

   Masking ensures right shifts do not propagate sign bit and loop terminates correctly.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Masking with 0xFFFFFFFF handles negative inputs correctly [OK]

Hint: Mask negative inputs to treat as unsigned [OK]

Common Mistakes:

• Using naive loop with signed shifts
• Taking absolute value loses bit pattern
• Left shift does not help counting bits

5. Suppose you want to check if a number is a power of two but the input can be negative or zero, and you want to handle 64-bit integers efficiently. Which modification to the bit manipulation approach is correct?

hard

A. Use the condition n > 0 and (n & (n - 1)) == 0 to handle all cases correctly.

B. Use n & (n + 1) == 0 to handle negative numbers as well.

C. Use floating point division to check if log2(n) is an integer for negative inputs.

D. Ignore negative inputs and only check positive numbers with n & (n - 1) == 0.

Solution

1. Step 1: Understand input constraints

   Negative and zero inputs are not powers of two, so must be excluded explicitly.

2. Step 2: Apply correct bit manipulation check

   Check n > 0 first, then use n & (n - 1) == 0 to verify exactly one set bit.

3. Step 3: Confirm correctness for 64-bit integers

   This approach works efficiently for 64-bit integers as well, since bitwise ops are constant time.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Explicit positive check avoids errors on zero/negative inputs [OK]

Hint: Always check n > 0 before bitwise power-of-two test [OK]

Common Mistakes:

• Using incorrect bitwise operations
• Ignoring negative inputs
• Using floating point logs causing precision errors