Maximum XOR of Two Numbers

🎯

Maximum XOR of Two Numbers

mediumBIT_MANIPULATIONAmazonGoogleFacebook

Imagine you have a list of secret codes represented as numbers, and you want to find the pair of codes that differ the most in their binary form to maximize security.

💡 This problem is about understanding how XOR works at the bit level and how to cleverly find two numbers that produce the largest XOR value. Beginners often struggle because the brute force approach is straightforward but inefficient, and the optimal solution requires a bitwise greedy strategy that is less intuitive.

📋

Problem Statement

Given an array of integers nums, find the maximum result of nums[i] XOR nums[j] where 0 ≤ i, j < n and i != j. Return the maximum XOR value.

1 ≤ n ≤ 10^50 ≤ nums[i] < 2^31

💡

Example

Input"[3, 10, 5, 25, 2, 8]"

Output28

The maximum XOR is 5 ^ 25 = 28.

• Array with all zeros → maximum XOR is 0
• Array with one element → maximum XOR is 0 (no pair)
• Array with two identical elements → maximum XOR is 0
• Array with maximum integer values → test handling of large bits

⚠️

Common Mistakes

Using brute force for large inputs

Code runs too slowly or times out

✅ Implement the greedy bit-by-bit or trie approach

Not masking prefixes correctly in greedy approach

Incorrect prefixes lead to wrong maximum XOR

✅ Ensure mask includes all bits from current bit to most significant bit

In trie approach, not checking for null children before traversal

Runtime errors or crashes

✅ Always check if child node exists before moving down the trie

Confusing XOR with OR or AND in logic

Wrong results, failing test cases

✅ Remember XOR properties and use ^ operator correctly

Not handling edge cases like single element arrays

Incorrect output or errors

✅ Return 0 when no pairs exist or handle gracefully

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by trying all pairs. It is simple but inefficient, helping beginners understand the problem's nature before optimizing.

Intuition

Try every possible pair of numbers and compute their XOR, keeping track of the maximum XOR found.

Algorithm

1. Initialize max_xor to 0.
2. Use two nested loops to iterate over all pairs (i, j) with i < j.
3. Calculate XOR of nums[i] and nums[j].
4. Update max_xor if the current XOR is greater.

💡 The nested loops make it easy to understand but hide the inefficiency until you analyze the time complexity.

</>

Code

def findMaximumXOR(nums):
    max_xor = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            current_xor = nums[i] ^ nums[j]
            if current_xor > max_xor:
                max_xor = current_xor
    return max_xor

# Driver code
if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

Line Notes

max_xor = 0Initialize the variable to keep track of the maximum XOR found so far.

for i in range(n)Outer loop selects the first number in the pair.

for j in range(i + 1, n)Inner loop selects the second number, avoiding duplicate pairs and self-pairing.

current_xor = nums[i] ^ nums[j]Calculate XOR of the current pair to check if it's the maximum.

public class Solution {
    public static int findMaximumXOR(int[] nums) {
        int maxXor = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int currentXor = nums[i] ^ nums[j];
                if (currentXor > maxXor) {
                    maxXor = currentXor;
                }
            }
        }
        return maxXor;
    }

    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(findMaximumXOR(nums)); // Output: 28
    }
}

Line Notes

int maxXor = 0;Initialize maxXor to store the maximum XOR found.

for (int i = 0; i < n; i++)Outer loop picks the first element of the pair.

for (int j = i + 1; j < n; j++)Inner loop picks the second element, ensuring no repeats or self-pairs.

int currentXor = nums[i] ^ nums[j];Compute XOR of the current pair to compare with maxXor.

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

int findMaximumXOR(vector<int>& nums) {
    int maxXor = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int currentXor = nums[i] ^ nums[j];
            if (currentXor > maxXor) {
                maxXor = currentXor;
            }
        }
    }
    return maxXor;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    cout << findMaximumXOR(nums) << endl; // Output: 28
    return 0;
}

Line Notes

int maxXor = 0;Initialize maxXor to track the highest XOR found.

for (int i = 0; i < n; i++)Outer loop selects the first number in the pair.

for (int j = i + 1; j < n; j++)Inner loop selects the second number, avoiding duplicates.

int currentXor = nums[i] ^ nums[j];Calculate XOR for the current pair to update maxXor if needed.

function findMaximumXOR(nums) {
    let maxXor = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const currentXor = nums[i] ^ nums[j];
            if (currentXor > maxXor) {
                maxXor = currentXor;
            }
        }
    }
    return maxXor;
}

// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // Output: 28

Line Notes

let maxXor = 0;Initialize maxXor to store the maximum XOR found so far.

for (let i = 0; i < n; i++)Outer loop picks the first element in the pair.

for (let j = i + 1; j < n; j++)Inner loop picks the second element, avoiding repeats and self-pairs.

const currentXor = nums[i] ^ nums[j];Calculate XOR of the current pair to check if it beats maxXor.

⏱

Complexity

TimeO(n^2)

SpaceO(1)

We check every pair of n elements, resulting in n*(n-1)/2 operations, which is O(n^2). No extra space is used except variables.

💡 For n=20, this means about 190 operations, which is manageable, but for n=100000, it becomes 5 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs, so it is useful only to understand the problem and as a baseline before optimizing.

🧠

Greedy Bit-by-Bit with Prefix Set

💡 This approach introduces a clever greedy strategy that builds the maximum XOR bit by bit from the most significant bit to the least, using a set of prefixes to check feasibility.

Intuition

Try to set the current bit in the answer to 1 if possible by checking if there exist two prefixes that can produce that bit set in XOR.

Algorithm

1. Initialize max_xor to 0.
2. Iterate from the highest bit (31) down to 0.
3. For each bit, build a set of prefixes of all numbers truncated to that bit.
4. Check if setting this bit in max_xor is possible by verifying if any two prefixes can produce that bit set in XOR.
5. If possible, update max_xor by setting this bit.

💡 This approach is tricky because it uses a greedy guess and set membership to confirm if the guess is valid, which is less intuitive than brute force.

</>

Code

def findMaximumXOR(nums):
    max_xor = 0
    mask = 0
    for i in range(31, -1, -1):
        mask |= (1 << i)
        prefixes = set([num & mask for num in nums])
        candidate = max_xor | (1 << i)
        for prefix in prefixes:
            if (candidate ^ prefix) in prefixes:
                max_xor = candidate
                break
    return max_xor

# Driver code
if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

Line Notes

max_xor = 0Initialize max_xor to store the maximum XOR found so far.

for i in range(31, -1, -1)Iterate over bits from the most significant (31) to least (0).

mask |= (1 << i)Update mask to include the current bit and all bits above it.

prefixes = set([num & mask for num in nums])Collect prefixes of all numbers truncated to current mask to check possible XOR pairs.

for prefix in prefixes:Check if there exists a pair of prefixes that can achieve the candidate XOR by leveraging XOR properties.

import java.util.*;

public class Solution {
    public static int findMaximumXOR(int[] nums) {
        int maxXor = 0, mask = 0;
        for (int i = 31; i >= 0; i--) {
            mask = mask | (1 << i);
            Set<Integer> prefixes = new HashSet<>();
            for (int num : nums) {
                prefixes.add(num & mask);
            }
            int candidate = maxXor | (1 << i);
            for (int prefix : prefixes) {
                if (prefixes.contains(candidate ^ prefix)) {
                    maxXor = candidate;
                    break;
                }
            }
        }
        return maxXor;
    }

    public static void main(String[] args) {
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(findMaximumXOR(nums)); // Output: 28
    }
}

Line Notes

int maxXor = 0, mask = 0;Initialize maxXor and mask to track maximum XOR and current bit mask.

for (int i = 31; i >= 0; i--)Iterate bits from highest to lowest to build maxXor bit by bit.

mask = mask | (1 << i);Update mask to include current bit and all higher bits.

Set<Integer> prefixes = new HashSet<>();Store prefixes truncated to current mask to check XOR feasibility.

for (int prefix : prefixes)Check if any two prefixes can produce the candidate XOR by XORing with each other.

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

int findMaximumXOR(vector<int>& nums) {
    int maxXor = 0, mask = 0;
    for (int i = 31; i >= 0; i--) {
        mask |= (1 << i);
        unordered_set<int> prefixes;
        for (int num : nums) {
            prefixes.insert(num & mask);
        }
        int candidate = maxXor | (1 << i);
        for (int prefix : prefixes) {
            if (prefixes.count(candidate ^ prefix)) {
                maxXor = candidate;
                break;
            }
        }
    }
    return maxXor;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    cout << findMaximumXOR(nums) << endl; // Output: 28
    return 0;
}

Line Notes

int maxXor = 0, mask = 0;Initialize maxXor and mask to track the maximum XOR and current bit mask.

for (int i = 31; i >= 0; i--)Iterate bits from most significant to least significant.

mask |= (1 << i);Update mask to include the current bit and all bits above it.

unordered_set<int> prefixes;Store prefixes truncated to the current mask to check if candidate XOR is possible.

for (int prefix : prefixes)Check if any two prefixes can produce the candidate XOR by XORing with each other.

function findMaximumXOR(nums) {
    let maxXor = 0, mask = 0;
    for (let i = 31; i >= 0; i--) {
        mask = mask | (1 << i);
        const prefixes = new Set();
        for (const num of nums) {
            prefixes.add(num & mask);
        }
        const candidate = maxXor | (1 << i);
        for (const prefix of prefixes) {
            if (prefixes.has(candidate ^ prefix)) {
                maxXor = candidate;
                break;
            }
        }
    }
    return maxXor;
}

// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // Output: 28

Line Notes

let maxXor = 0, mask = 0;Initialize maxXor and mask to track the maximum XOR and current bit mask.

for (let i = 31; i >= 0; i--)Iterate bits from highest to lowest to build maxXor bit by bit.

mask = mask | (1 << i);Update mask to include the current bit and all bits above it.

const prefixes = new Set();Store prefixes truncated to current mask to check if candidate XOR is possible.

for (const prefix of prefixes)Check if any two prefixes can produce the candidate XOR by XORing with each other.

⏱

Complexity

TimeO(n * log M)

SpaceO(n)

We iterate over 32 bits (log M where M is max number), and for each bit, we build a set of prefixes of size n, resulting in O(n * log M) time. Space is O(n) for the prefix set.

💡 For n=100000 and 32 bits, this means about 3.2 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This is the optimal approach for this problem and is expected in interviews to demonstrate bit manipulation mastery.

🧠

Trie-Based Bitwise Solution

💡 This approach uses a binary trie (prefix tree) to store numbers bit by bit, allowing efficient queries to find the best XOR partner for each number.

Intuition

Insert all numbers into a trie representing bits from most significant to least. For each number, traverse the trie to greedily pick opposite bits to maximize XOR.

Algorithm

1. Build a trie with all numbers inserted bit by bit from the 31st to 0th bit.
2. For each number, traverse the trie to find the number that maximizes XOR by choosing opposite bits when possible.
3. Keep track of the maximum XOR found during these traversals.
4. Return the maximum XOR after processing all numbers.

💡 This approach is more complex due to the trie data structure but offers clear logic for maximizing XOR bitwise.

</>

Code

class TrieNode:
    def __init__(self):
        self.children = {}

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, num):
        node = self.root
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            if bit not in node.children:
                node.children[bit] = TrieNode()
            node = node.children[bit]

    def findMaxXor(self, num):
        node = self.root
        max_xor = 0
        for i in range(31, -1, -1):
            bit = (num >> i) & 1
            toggled_bit = 1 - bit
            if toggled_bit in node.children:
                max_xor |= (1 << i)
                node = node.children[toggled_bit]
            else:
                node = node.children.get(bit)
        return max_xor

def findMaximumXOR(nums):
    trie = Trie()
    for num in nums:
        trie.insert(num)
    max_xor = 0
    for num in nums:
        max_xor = max(max_xor, trie.findMaxXor(num))
    return max_xor

# Driver code
if __name__ == '__main__':
    nums = [3, 10, 5, 25, 2, 8]
    print(findMaximumXOR(nums))  # Output: 28

Line Notes

class TrieNode:Define a node in the trie with children for bits 0 and 1.

def insert(self, num):Insert a number into the trie bit by bit from MSB to LSB.

def findMaxXor(self, num):Find the maximum XOR for num by traversing trie choosing opposite bits when possible.

max_xor = max(max_xor, trie.findMaxXor(num))Update global maximum XOR after checking each number.

for i in range(31, -1, -1):Traverse bits from most significant to least significant to find best XOR path.

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[2];
}

public class Solution {
    TrieNode root = new TrieNode();

    public void insert(int num) {
        TrieNode node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (node.children[bit] == null) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }

    public int findMaxXor(int num) {
        TrieNode node = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node.children[toggledBit] != null) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }

    public int findMaximumXOR(int[] nums) {
        for (int num : nums) insert(num);
        int maxXor = 0;
        for (int num : nums) {
            maxXor = Math.max(maxXor, findMaxXor(num));
        }
        return maxXor;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 10, 5, 25, 2, 8};
        System.out.println(sol.findMaximumXOR(nums)); // Output: 28
    }
}

Line Notes

TrieNode[] children = new TrieNode[2];Each node has two children representing bits 0 and 1.

for (int i = 31; i >= 0; i--)Traverse bits from most significant to least significant to find best XOR path.

if (node.children[toggledBit] != null)Try to go opposite bit to maximize XOR at this bit position.

maxXor = Math.max(maxXor, findMaxXor(num));Update maximum XOR after querying trie for each number.

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

struct TrieNode {
    TrieNode* children[2] = {nullptr, nullptr};
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(int num) {
        TrieNode* node = root;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
        }
    }

    int findMaxXor(int num) {
        TrieNode* node = root;
        int maxXor = 0;
        for (int i = 31; i >= 0; i--) {
            int bit = (num >> i) & 1;
            int toggledBit = 1 - bit;
            if (node->children[toggledBit]) {
                maxXor |= (1 << i);
                node = node->children[toggledBit];
            } else {
                node = node->children[bit];
            }
        }
        return maxXor;
    }
};

int findMaximumXOR(vector<int>& nums) {
    Trie trie;
    for (int num : nums) trie.insert(num);
    int maxXor = 0;
    for (int num : nums) {
        maxXor = max(maxXor, trie.findMaxXor(num));
    }
    return maxXor;
}

int main() {
    vector<int> nums = {3, 10, 5, 25, 2, 8};
    cout << findMaximumXOR(nums) << endl; // Output: 28
    return 0;
}

Line Notes

TrieNode* children[2] = {nullptr, nullptr};Each trie node has two children for bits 0 and 1.

for (int i = 31; i >= 0; i--)Traverse bits from most significant to least significant to find best XOR path.

if (node->children[toggledBit])Try to go opposite bit to maximize XOR at this bit position.

maxXor = max(maxXor, trie.findMaxXor(num));Update maximum XOR after querying trie for each number.

class TrieNode {
    constructor() {
        this.children = {};
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(num) {
        let node = this.root;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            if (!(bit in node.children)) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
        }
    }

    findMaxXor(num) {
        let node = this.root;
        let maxXor = 0;
        for (let i = 31; i >= 0; i--) {
            const bit = (num >> i) & 1;
            const toggledBit = 1 - bit;
            if (toggledBit in node.children) {
                maxXor |= (1 << i);
                node = node.children[toggledBit];
            } else {
                node = node.children[bit];
            }
        }
        return maxXor;
    }
}

function findMaximumXOR(nums) {
    const trie = new Trie();
    for (const num of nums) trie.insert(num);
    let maxXor = 0;
    for (const num of nums) {
        maxXor = Math.max(maxXor, trie.findMaxXor(num));
    }
    return maxXor;
}

// Test
const nums = [3, 10, 5, 25, 2, 8];
console.log(findMaximumXOR(nums)); // Output: 28

Line Notes

this.children = {};Each trie node stores children for bits 0 and 1 as keys.

for (let i = 31; i >= 0; i--)Traverse bits from most significant to least significant to find best XOR path.

if (toggledBit in node.children)Try to go opposite bit to maximize XOR at this bit position.

maxXor = Math.max(maxXor, trie.findMaxXor(num));Update maximum XOR after querying trie for each number.

⏱

Complexity

TimeO(n * log M)

SpaceO(n * log M)

Inserting n numbers into a trie with log M bits each takes O(n log M). Querying each number also takes O(log M). Space is O(n log M) for the trie nodes.

💡 For n=100000 and 32 bits, this is efficient but uses more memory than the prefix set approach.

Interview Verdict: Accepted

This approach is optimal and demonstrates mastery of tries and bit manipulation, useful for advanced interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the greedy bit-by-bit approach is best as it balances clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code for large inputs
2. Greedy Bit-by-Bit with Prefix Set	O(n * log M)	O(n)	No	No	Code this for optimal solution
3. Trie-Based Bitwise Solution	O(n * log M)	O(n * log M)	No	No	Mention as alternative optimal solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start with brute force to build intuition, then learn the greedy bit-by-bit approach, and finally the trie method for mastery.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach and its inefficiency.Step 3: Introduce the greedy bit-by-bit approach with prefix sets.Step 4: Optionally discuss the trie-based solution for completeness.Step 5: Code the greedy bit-by-bit approach and test.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of bit manipulation, ability to optimize brute force, and knowledge of greedy and trie data structures.

Common Follow-ups

• What if numbers are very large? → Use 64-bit or adjust bit range accordingly.
• Can you find the pair of numbers that produce the max XOR? → Store indices or numbers during computation.

💡 Follow-ups test your ability to adapt the solution to variations and extract additional information beyond the maximum XOR value.

🔍

Pattern Recognition

When to Use

1) Problem asks for maximum XOR of two numbers; 2) Input is an array of integers; 3) Constraints allow bitwise operations; 4) Naive O(n^2) is too slow.

Signature Phrases

maximum XORtwo numbersbitwise XOR maximize

NOT This Pattern When

Problems that ask for sum or AND maximums, or those that do not involve bitwise XOR.

Similar Problems

Maximum XOR of Two Numbers in an Array - same core problemSingle Number - uses XOR propertiesFind Maximum XOR of Two Numbers in an Array - variant with similar approach

Practice

1. What is the time complexity of the XOR partitioning approach to find two missing numbers from 1 to n given an array of size n-2?

medium

A. O(n²) due to nested loops over the range and array

B. O(n) because it iterates over the range and array a constant number of times

C. O(n log n) due to bitwise operations on each element

D. O(1) since XOR operations are constant time

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over the range 1 to n once and over the input array once, each in separate loops.

2. Step 2: Analyze operations inside loops

   Each iteration performs constant time XOR and bitwise operations, so total time is proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes -> O(n) time [OK]

Hint: Count loops and operations per iteration carefully [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Thinking bitwise ops add log n factor
• Confusing constant time with O(1) overall

2. The following code attempts to find the maximum product of word lengths with no common letters. Which line contains a subtle bug that can cause incorrect results or inefficiency?

medium

A. Line 18: Checking bitmask overlap with bitwise AND

B. Line 10: Sorting masks by length in descending order

C. Line 14: Breaking outer loop when max product cannot improve

D. Line 6: Incorrect bit shift by adding 1 to character index

Solution

1. Step 1: Identify bitmask construction

   Line 6 shifts bits by (ord(ch) - ord('a') + 1), which incorrectly shifts by 1 extra, causing wrong bitmask representation.

2. Step 2: Impact of incorrect bitmask

   This causes overlap checks to fail or miss common letters, leading to incorrect max product or missed pruning opportunities.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bitmask must shift by (ord(ch) - ord('a')) exactly [OK]

Hint: Bit shift must match character index exactly [OK]

Common Mistakes:

• Off-by-one bit shifting in bitmask
• Not pruning pairs after sorting
• Incorrect overlap check logic

3. What is the time complexity of the brute force bit counting approach that checks each bit of a 32-bit integer one by one?

medium

A. O(log n) where n is the integer's value

B. O(n) where n is the integer's value

C. O(1) because the number of bits is fixed (32 bits)

D. O(32 * log n) due to bit shifts and counting

Solution

1. Step 1: Identify input size

   The input is an integer n, and the brute force method checks each bit by shifting until n becomes zero.

2. Step 2: Analyze loop iterations

   The number of iterations depends on the number of bits in n, which is proportional to log n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Loop runs approximately log n times, so complexity is O(log n) [OK]

Hint: Number of bits in n is proportional to log n [OK]

Common Mistakes:

• Assuming fixed bit width means O(1)
• Confusing value magnitude with fixed bit size

4. What is the time complexity of the optimal XOR and partition approach to find two unique numbers in an array of size n?

medium

A. O(n log n) due to sorting step

B. O(n) because it traverses the array a constant number of times

C. O(n^2) because of nested loops in partitioning

D. O(n) but uses O(n) extra space for partitions

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm traverses the array twice: once to XOR all elements, once to partition and XOR groups.

2. Step 2: Analyze time and space complexity

   Each traversal is O(n), no nested loops. Space used is constant (variables only), no extra arrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two linear passes, constant space [OK]

Hint: Two passes over array -> O(n) time, O(1) space [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming nested loops in partition
• Forgetting constant space usage

5. Suppose you want to extend the sum of two integers without using + operator to support arbitrary large integers beyond 32 bits. Which modification is necessary to ensure correctness?

hard

A. Use built-in + operator for large integers since bitwise approach only works for fixed 32-bit integers.

B. Keep masking with 0xFFFFFFFF but increase mask size dynamically based on input bit length.

C. Implement iterative approach without recursion to avoid stack overflow on large inputs.

D. Remove masking with 0xFFFFFFFF to allow Python's unlimited integer size to handle sums.

Solution

1. Step 1: Identify recursion depth issue

   For very large integers, recursion depth grows with bit length, risking stack overflow.

2. Step 2: Use iterative approach to handle arbitrary large integers

   Iterative bitwise sum avoids recursion stack limits and handles large inputs safely.

3. Step 3: Masking must adapt or be removed carefully

   Masking fixed to 32 bits breaks large integer sums; iterative approach can handle masking dynamically.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Iterative avoids recursion limits for large inputs [OK]

Hint: Recursion depth limits large input sums; iteration needed [OK]

Common Mistakes:

• Removing mask blindly breaks sign handling
• Using + operator defeats problem purpose
• Static mask size limits input range