Maximum Product of Word Lengths

🎯

Maximum Product of Word Lengths

mediumBIT_MANIPULATIONAmazonGoogleFacebook

Imagine you have a list of words and want to find two that don't share any letters, maximizing the product of their lengths - like pairing two puzzle pieces that fit perfectly without overlap.

💡 This problem requires checking if two words share common letters efficiently. Beginners often struggle because comparing every character pair is slow. Using bit manipulation to represent character sets as bits makes these checks fast and elegant.

📋

Problem Statement

Given an array of strings words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share any common letters. Return 0 if no such pair exists.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 1000words[i] consists only of lowercase English letters

💡

Example

Input"[\"abcw\",\"baz\",\"foo\",\"bar\",\"xtfn\",\"abcdef\"]"

Output16

The two words "abcw" and "xtfn" do not share common letters and their lengths multiply to 4 * 4 = 16, which is the maximum.

• All words share at least one common letter → output 0
• Only one word in the list → output 0
• Words with repeated letters but no overlap with others → product based on length
• Words with maximum length (1000 characters) → ensure performance

⚠️

Common Mistakes

Checking common letters by scanning all characters instead of bitmasking

Solution is too slow and times out on large inputs

✅ Use bitmasking to represent character sets and check overlap with bitwise AND

Not pruning pairs after sorting by length

Unnecessary checks increase runtime, causing inefficiency

✅ Break inner loops early when product cannot exceed current max

Incorrect bit shifting causing wrong bitmask

Incorrect overlap checks lead to wrong answers

✅ Ensure bit shift is (ord(ch) - ord('a')) or (c - 'a') for lowercase letters

Not handling empty or single-word input

Returns incorrect result or crashes

✅ Return 0 if less than two words or no valid pairs

🧠

Brute Force (Nested Loops with Character Set Checks)

💡 This approach is the foundation: it checks every pair of words for common letters by scanning characters. It’s slow but helps understand the problem deeply before optimizing.

Intuition

Check every pair of words and verify if they share any letter by comparing their characters. If no common letter, calculate product of lengths and track the maximum.

Algorithm

1. Iterate over all pairs of words using two nested loops.
2. For each pair, check if they share any common character by scanning all characters.
3. If no common character is found, calculate the product of their lengths.
4. Keep track of the maximum product found and return it at the end.

💡 The nested loops and character checks are straightforward but inefficient, which helps grasp the problem’s core before improving.

</>

Code

def maxProduct(words):
    max_prod = 0
    n = len(words)
    for i in range(n):
        for j in range(i + 1, n):
            if not share_common_char(words[i], words[j]):
                max_prod = max(max_prod, len(words[i]) * len(words[j]))
    return max_prod

def share_common_char(w1, w2):
    set1 = set(w1)
    set2 = set(w2)
    for ch in set1:
        if ch in set2:
            return True
    return False

# Driver code
if __name__ == '__main__':
    words = ["abcw","baz","foo","bar","xtfn","abcdef"]
    print(maxProduct(words))  # Output: 16

Line Notes

max_prod = 0Initialize max product to zero to track the best pair found

for i in range(n)Outer loop picks the first word

for j in range(i + 1, n)Inner loop picks the second word to form pairs without repetition

if not share_common_char(words[i], words[j])Check if the two words share no common letters before calculating product

set1 = set(w1)Convert first word to a set for quick membership checks

for ch in set1Iterate over unique characters to check overlap

if ch in set2If any character is common, return True to skip this pair

return max_prodReturn the maximum product found after checking all pairs

import java.util.*;
public class Solution {
    public static int maxProduct(String[] words) {
        int maxProd = 0;
        int n = words.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (!shareCommonChar(words[i], words[j])) {
                    maxProd = Math.max(maxProd, words[i].length() * words[j].length());
                }
            }
        }
        return maxProd;
    }

    private static boolean shareCommonChar(String w1, String w2) {
        Set<Character> set1 = new HashSet<>();
        for (char c : w1.toCharArray()) set1.add(c);
        for (char c : w2.toCharArray()) {
            if (set1.contains(c)) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String[] words = {"abcw","baz","foo","bar","xtfn","abcdef"};
        System.out.println(maxProduct(words)); // Output: 16
    }
}

Line Notes

int maxProd = 0;Initialize max product to zero to track best pair

for (int i = 0; i < n; i++)Outer loop selects first word

for (int j = i + 1; j < n; j++)Inner loop selects second word to avoid duplicates

if (!shareCommonChar(words[i], words[j]))Check if words share no common letters before product calculation

Set<Character> set1 = new HashSet<>();Use a HashSet for quick character lookup

for (char c : w2.toCharArray())Check each character of second word against first word's set

if (set1.contains(c)) return true;Return early if common character found

return maxProd;Return maximum product after all pairs checked

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

bool shareCommonChar(const string& w1, const string& w2) {
    unordered_set<char> set1(w1.begin(), w1.end());
    for (char c : w2) {
        if (set1.count(c)) return true;
    }
    return false;
}

int maxProduct(vector<string>& words) {
    int maxProd = 0;
    int n = words.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (!shareCommonChar(words[i], words[j])) {
                maxProd = max(maxProd, (int)words[i].size() * (int)words[j].size());
            }
        }
    }
    return maxProd;
}

int main() {
    vector<string> words = {"abcw","baz","foo","bar","xtfn","abcdef"};
    cout << maxProduct(words) << endl; // Output: 16
    return 0;
}

Line Notes

int maxProd = 0;Initialize max product to zero for tracking

for (int i = 0; i < n; i++)Outer loop picks first word

for (int j = i + 1; j < n; j++)Inner loop picks second word to avoid repeats

if (!shareCommonChar(words[i], words[j]))Check if words share no common letters before product calculation

unordered_set<char> set1(w1.begin(), w1.end());Create a hash set of characters from first word for quick lookup

for (char c : w2)Iterate characters of second word to check overlap

if (set1.count(c)) return true;Return early if common character found

return maxProd;Return maximum product after all pairs checked

function maxProduct(words) {
    let maxProd = 0;
    const n = words.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (!shareCommonChar(words[i], words[j])) {
                maxProd = Math.max(maxProd, words[i].length * words[j].length);
            }
        }
    }
    return maxProd;
}

function shareCommonChar(w1, w2) {
    const set1 = new Set(w1);
    for (const ch of w2) {
        if (set1.has(ch)) return true;
    }
    return false;
}

// Driver code
const words = ["abcw","baz","foo","bar","xtfn","abcdef"];
console.log(maxProduct(words)); // Output: 16

Line Notes

let maxProd = 0;Initialize max product to zero for tracking best pair

for (let i = 0; i < n; i++)Outer loop selects first word

for (let j = i + 1; j < n; j++)Inner loop selects second word to avoid duplicate pairs

if (!shareCommonChar(words[i], words[j]))Check if words share no common letters before product calculation

const set1 = new Set(w1);Create a set of characters from first word for quick membership checks

for (const ch of w2)Iterate characters of second word to check overlap

if (set1.has(ch)) return true;Return early if common character found

return maxProd;Return maximum product after all pairs checked

⏱

Complexity

TimeO(n^2 * k) where n is number of words and k is average word length

SpaceO(k) for sets used in character checks

We check every pair of words (n^2) and for each pair, we scan characters (k) to check overlap.

💡 For n=1000 and k=10, this means about 1,000,000 * 10 = 10 million operations, which is slow for large inputs.

Interview Verdict: TLE / Use only to introduce problem and intuition

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

🧠

Bitmasking to Represent Character Sets

💡 Using bitmasks to represent each word’s character set allows constant time checks for common letters, drastically improving efficiency.

Intuition

Represent each word as a 26-bit integer where each bit corresponds to a letter. Two words share no letters if bitwise AND of their masks is zero.

Algorithm

1. Convert each word into a bitmask integer representing its letters.
2. Iterate over all pairs of bitmasks.
3. If bitwise AND of two masks is zero, update max product with lengths of corresponding words.
4. Return the maximum product found.

💡 Bitmasking reduces the costly character comparisons to fast bitwise operations, making pair checks efficient.

</>

Code

def maxProduct(words):
    n = len(words)
    masks = [0] * n
    lengths = [0] * n
    for i, word in enumerate(words):
        mask = 0
        for ch in word:
            mask |= 1 << (ord(ch) - ord('a'))
        masks[i] = mask
        lengths[i] = len(word)

    max_prod = 0
    for i in range(n):
        for j in range(i + 1, n):
            if (masks[i] & masks[j]) == 0:
                max_prod = max(max_prod, lengths[i] * lengths[j])
    return max_prod

# Driver code
if __name__ == '__main__':
    words = ["abcw","baz","foo","bar","xtfn","abcdef"]
    print(maxProduct(words))  # Output: 16

Line Notes

masks = [0] * nInitialize list to store bitmasks for each word

for ch in wordSet bit corresponding to each character in the word

mask |= 1 << (ord(ch) - ord('a'))Use bitwise OR to set bit for character

if (masks[i] & masks[j]) == 0Check if two words share no common letters using bitwise AND

max_prod = max(max_prod, lengths[i] * lengths[j])Update max product if no overlap

public class Solution {
    public static int maxProduct(String[] words) {
        int n = words.length;
        int[] masks = new int[n];
        int[] lengths = new int[n];
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i].toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            masks[i] = mask;
            lengths[i] = words[i].length();
        }

        int maxProd = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if ((masks[i] & masks[j]) == 0) {
                    maxProd = Math.max(maxProd, lengths[i] * lengths[j]);
                }
            }
        }
        return maxProd;
    }

    public static void main(String[] args) {
        String[] words = {"abcw","baz","foo","bar","xtfn","abcdef"};
        System.out.println(maxProduct(words)); // Output: 16
    }
}

Line Notes

int[] masks = new int[n];Array to store bitmask for each word

mask |= 1 << (c - 'a');Set bit for character c in mask

if ((masks[i] & masks[j]) == 0)Check if two words share no letters by bitwise AND

maxProd = Math.max(maxProd, lengths[i] * lengths[j]);Update max product if no overlap

return maxProd;Return maximum product after checking all pairs

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

int maxProduct(vector<string>& words) {
    int n = words.size();
    vector<int> masks(n, 0);
    vector<int> lengths(n, 0);
    for (int i = 0; i < n; i++) {
        int mask = 0;
        for (char c : words[i]) {
            mask |= 1 << (c - 'a');
        }
        masks[i] = mask;
        lengths[i] = words[i].size();
    }

    int maxProd = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) == 0) {
                maxProd = max(maxProd, lengths[i] * lengths[j]);
            }
        }
    }
    return maxProd;
}

int main() {
    vector<string> words = {"abcw","baz","foo","bar","xtfn","abcdef"};
    cout << maxProduct(words) << endl; // Output: 16
    return 0;
}

Line Notes

vector<int> masks(n, 0);Store bitmask for each word

mask |= 1 << (c - 'a');Set bit for character in mask

if ((masks[i] & masks[j]) == 0)Check if two words share no letters using bitwise AND

maxProd = max(maxProd, lengths[i] * lengths[j]);Update max product if no overlap

return maxProd;Return maximum product after all pairs checked

function maxProduct(words) {
    const n = words.length;
    const masks = new Array(n).fill(0);
    const lengths = new Array(n).fill(0);
    for (let i = 0; i < n; i++) {
        let mask = 0;
        for (const ch of words[i]) {
            mask |= 1 << (ch.charCodeAt(0) - 97);
        }
        masks[i] = mask;
        lengths[i] = words[i].length;
    }

    let maxProd = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if ((masks[i] & masks[j]) === 0) {
                maxProd = Math.max(maxProd, lengths[i] * lengths[j]);
            }
        }
    }
    return maxProd;
}

// Driver code
const words = ["abcw","baz","foo","bar","xtfn","abcdef"];
console.log(maxProduct(words)); // Output: 16

Line Notes

const masks = new Array(n).fill(0);Initialize array to store bitmasks

mask |= 1 << (ch.charCodeAt(0) - 97);Set bit for character in mask

if ((masks[i] & masks[j]) === 0)Check if two words share no letters using bitwise AND

maxProd = Math.max(maxProd, lengths[i] * lengths[j]);Update max product if no overlap

return maxProd;Return maximum product after all pairs checked

⏱

Complexity

TimeO(n^2 + n*k) where n is number of words and k is average word length

SpaceO(n) for storing bitmasks and lengths

Bitmask creation takes O(n*k), pairwise checks take O(n^2) but are faster due to bitwise operations.

💡 For n=1000 and k=10, this is roughly 1,000,000 operations, which is feasible in interviews.

Interview Verdict: Accepted / Efficient for medium-sized inputs

This approach is efficient and commonly accepted in interviews, showing mastery of bit manipulation.

🧠

Bitmasking with Length Sorting and Early Pruning

💡 Sorting words by length allows early pruning of pairs that cannot beat the current max product, improving efficiency.

Intuition

Sort words by length descending. When checking pairs, if product of lengths is less than current max, skip further checks.

Algorithm

1. Convert each word to a bitmask and store its length.
2. Sort words by length descending.
3. Iterate over pairs; if product of lengths is less than current max, break inner loop early.
4. If bitmasks have no common letters, update max product.
5. Return the maximum product found.

💡 Sorting and pruning reduce unnecessary checks, speeding up the solution especially when many words are short.

</>

Code

def maxProduct(words):
    n = len(words)
    masks = []
    for word in words:
        mask = 0
        for ch in word:
            mask |= 1 << (ord(ch) - ord('a'))
        masks.append((mask, len(word)))

    masks.sort(key=lambda x: x[1], reverse=True)

    max_prod = 0
    for i in range(n):
        if masks[i][1] * masks[i][1] <= max_prod:
            break
        for j in range(i + 1, n):
            if masks[i][1] * masks[j][1] <= max_prod:
                break
            if (masks[i][0] & masks[j][0]) == 0:
                max_prod = max(max_prod, masks[i][1] * masks[j][1])
    return max_prod

# Driver code
if __name__ == '__main__':
    words = ["abcw","baz","foo","bar","xtfn","abcdef"]
    print(maxProduct(words))  # Output: 16

Line Notes

masks.append((mask, len(word)))Store tuple of bitmask and word length for sorting

masks.sort(key=lambda x: x[1], reverse=True)Sort words by length descending to prune early

if masks[i][1] * masks[i][1] <= max_prodIf max possible product with current word is less than max, break outer loop

if masks[i][1] * masks[j][1] <= max_prodPrune inner loop if product can't beat max product

if (masks[i][0] & masks[j][0]) == 0Check if words share no letters using bitwise AND

import java.util.*;
public class Solution {
    public static int maxProduct(String[] words) {
        int n = words.length;
        int[][] masks = new int[n][2];
        for (int i = 0; i < n; i++) {
            int mask = 0;
            for (char c : words[i].toCharArray()) {
                mask |= 1 << (c - 'a');
            }
            masks[i][0] = mask;
            masks[i][1] = words[i].length();
        }

        Arrays.sort(masks, (a, b) -> b[1] - a[1]);

        int maxProd = 0;
        for (int i = 0; i < n; i++) {
            if (masks[i][1] * masks[i][1] <= maxProd) break;
            for (int j = i + 1; j < n; j++) {
                if (masks[i][1] * masks[j][1] <= maxProd) break;
                if ((masks[i][0] & masks[j][0]) == 0) {
                    maxProd = Math.max(maxProd, masks[i][1] * masks[j][1]);
                }
            }
        }
        return maxProd;
    }

    public static void main(String[] args) {
        String[] words = {"abcw","baz","foo","bar","xtfn","abcdef"};
        System.out.println(maxProduct(words)); // Output: 16
    }
}

Line Notes

int[][] masks = new int[n][2];Store bitmask and length pairs

Arrays.sort(masks, (a, b) -> b[1] - a[1]);Sort by length descending for pruning

if (masks[i][1] * masks[i][1] <= maxProd) break;Prune outer loop if max possible product is less than current max

if (masks[i][1] * masks[j][1] <= maxProd) break;Prune inner loop similarly

if ((masks[i][0] & masks[j][0]) == 0)Check no common letters using bitwise AND

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

int maxProduct(vector<string>& words) {
    int n = words.size();
    vector<pair<int,int>> masks(n);
    for (int i = 0; i < n; i++) {
        int mask = 0;
        for (char c : words[i]) {
            mask |= 1 << (c - 'a');
        }
        masks[i] = {mask, (int)words[i].size()};
    }

    sort(masks.begin(), masks.end(), [](auto &a, auto &b) {
        return a.second > b.second;
    });

    int maxProd = 0;
    for (int i = 0; i < n; i++) {
        if (masks[i].second * masks[i].second <= maxProd) break;
        for (int j = i + 1; j < n; j++) {
            if (masks[i].second * masks[j].second <= maxProd) break;
            if ((masks[i].first & masks[j].first) == 0) {
                maxProd = max(maxProd, masks[i].second * masks[j].second);
            }
        }
    }
    return maxProd;
}

int main() {
    vector<string> words = {"abcw","baz","foo","bar","xtfn","abcdef"};
    cout << maxProduct(words) << endl; // Output: 16
    return 0;
}

Line Notes

vector<pair<int,int>> masks(n);Store bitmask and length pairs

sort(masks.begin(), masks.end(), [](auto &a, auto &b)Sort by length descending for pruning

if (masks[i].second * masks[i].second <= maxProd) break;Prune outer loop if max possible product is less than current max

if (masks[i].second * masks[j].second <= maxProd) break;Prune inner loop similarly

if ((masks[i].first & masks[j].first) == 0)Check no common letters using bitwise AND

function maxProduct(words) {
    const n = words.length;
    const masks = [];
    for (let word of words) {
        let mask = 0;
        for (const ch of word) {
            mask |= 1 << (ch.charCodeAt(0) - 97);
        }
        masks.push([mask, word.length]);
    }

    masks.sort((a, b) => b[1] - a[1]);

    let maxProd = 0;
    for (let i = 0; i < n; i++) {
        if (masks[i][1] * masks[i][1] <= maxProd) break;
        for (let j = i + 1; j < n; j++) {
            if (masks[i][1] * masks[j][1] <= maxProd) break;
            if ((masks[i][0] & masks[j][0]) === 0) {
                maxProd = Math.max(maxProd, masks[i][1] * masks[j][1]);
            }
        }
    }
    return maxProd;
}

// Driver code
const words = ["abcw","baz","foo","bar","xtfn","abcdef"];
console.log(maxProduct(words)); // Output: 16

Line Notes

const masks = [];Store bitmask and length pairs

masks.sort((a, b) => b[1] - a[1]);Sort by length descending for pruning

if (masks[i][1] * masks[i][1] <= maxProd) break;Prune outer loop if max possible product is less than current max

if (masks[i][1] * masks[j][1] <= maxProd) break;Prune inner loop similarly

if ((masks[i][0] & masks[j][0]) === 0)Check no common letters using bitwise AND

⏱

Complexity

TimeO(n^2 + n*k + n log n) where n is number of words and k is average word length

SpaceO(n) for bitmask and length storage

Sorting adds O(n log n), bitmask creation O(n*k), and pairwise checks O(n^2) with pruning to reduce actual checks.

💡 This approach is faster than plain bitmasking for large inputs due to pruning, making it practical for interviews.

Interview Verdict: Accepted / Most efficient practical solution

This approach balances clarity and efficiency, making it ideal to implement in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the bitmasking with sorting and pruning approach in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2 * k)	O(k)	No	N/A	Mention only - never code due to inefficiency
2. Bitmasking	O(n^2 + n*k)	O(n)	No	N/A	Code if input size is moderate
3. Bitmasking with Sorting and Pruning	O(n^2 + n*k + n log n)	O(n)	No	N/A	Preferred approach to implement in interviews

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding each approach, and learn how to communicate your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Introduce bitmasking to optimize character overlap checks.Step 4: Explain sorting and pruning to further improve efficiency.Step 5: Code the final optimized solution and test with examples.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your ability to optimize naive solutions, use bit manipulation effectively, and handle edge cases and large inputs.

Common Follow-ups

• What if words contain uppercase letters? → Normalize to lowercase or extend bitmask size.
• Can you reduce space usage? → Use in-place bitmasking or compress data.
• How to handle very large word lists? → Use pruning and early breaks aggressively.
• What if words contain non-English letters? → Use larger bitmasks or hash sets.

💡 These follow-ups test your adaptability and deeper understanding of bit manipulation and optimization.

🔍

Pattern Recognition

When to Use

1) Need to check if two strings share common characters efficiently, 2) Input size is large, 3) Characters are limited (e.g., lowercase letters), 4) Problem asks for maximum/minimum product or sum based on non-overlapping sets.

Signature Phrases

do not share any common lettersmaximum product of lengthscheck overlap efficiently

NOT This Pattern When

Problems that require substring or subsequence DP without character set overlap checks

Similar Problems

Maximum XOR of Two Numbers in an Array - uses bit manipulation to optimize pair checksLongest Substring Without Repeating Characters - uses bitmask or sliding window to track characters

Practice

1. You need to compute the number of set bits (1s) in the binary representation of every integer from 0 up to a given number N efficiently. Which approach guarantees the optimal time complexity for this problem?

easy

A. Use Brian Kernighan's bit counting trick to count set bits for each number by repeatedly clearing the least significant set bit.

B. Use a dynamic programming approach that counts bits by building results from smaller subproblems using right shifts.

C. Use a greedy approach that counts bits by checking each bit position independently for all numbers.

D. Convert each number to a binary string and count the '1' characters using built-in string functions.

Solution

1. Step 1: Understand the problem requirements

   The problem requires counting set bits for all numbers from 0 to N efficiently.

2. Step 2: Evaluate approaches for optimality

   Brian Kernighan's trick counts set bits per number in O(k) time, where k is the number of set bits, but doing this for all numbers results in O(n log n) in worst case. The dynamic programming approach uses previously computed results and right shifts to achieve O(n) time complexity, which is optimal.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   DP approach is optimal for counting bits from 0 to N [OK]

Hint: DP approach builds on smaller subproblems for O(n) time [OK]

Common Mistakes:

• Assuming Brian Kernighan's trick is optimal for all numbers
• Using string conversion for speed
• Greedy bit checking is optimal

2. Consider the following Python function that reverses bits of a 32-bit unsigned integer using divide and conquer masks:

def reverseBits(n: int) -> int:
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    n = ((n >> 16) | (n << 16)) & 0xffffffff
    return n

print(reverseBits(11))  # Input is 11 (binary 00000000000000000000000000001011)

What is the output of this code?

easy

A. 2952790016

B. 3758096384

C. 2147483648

D. 3221225472

Solution

1. Step 1: Convert input to binary

   11 in 32-bit binary is 00000000000000000000000000001011.

2. Step 2: Reverse bits using masks

   Reversing bits yields 11010000000000000000000000000000, which is 2952790016 in decimal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary reversal matches decimal 2952790016 [OK]

Hint: Reverse bits of 11 -> 2952790016 decimal [OK]

Common Mistakes:

• Confusing left and right shifts
• Forgetting to mask final result to 32 bits
• Miscounting bit positions

3. Identify the bug in the following code snippet for bitwise AND of numbers range:

medium

A. The bit-clearing operation 'right = right & (right - 1)' is incorrect.

B. There is no bug; the code works correctly.

C. The function should return 'left' instead of 'right'.

D. The loop condition should be 'right > left' instead of 'right != left'.

Solution

1. Step 1: Analyze loop condition

   The loop runs while right != left, which fails if right < left, causing infinite loop or incorrect behavior.

2. Step 2: Correct condition

   Changing condition to 'right > left' ensures loop terminates when right reaches or goes below left.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Loop condition must prevent infinite loops and handle equality correctly [OK]

Hint: Loop condition must be 'right > left' to terminate properly [OK]

Common Mistakes:

• Using '!=' instead of '>' causes infinite loops
• Misunderstanding bit-clearing operation
• Returning wrong variable

4. What is the time complexity of the trie-based maximum XOR algorithm for an input array of size n, where each number fits in 32 bits?

medium

A. O(n^2)

B. O(n * log M), where M is the max number value

C. O(n * 32^2)

D. O(n * 32)

Solution

1. Step 1: Identify operations per number

   Each number is inserted into the trie by processing 32 bits, so insertion is O(32) per number.

2. Step 2: Find max XOR per number

   For each number, traversing trie to find max XOR also takes O(32) steps.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity is O(n * 32) = O(n), since 32 is constant [OK]

Hint: 32 bits fixed, so linear in n [OK]

Common Mistakes:

• Confusing log M with n
• Assuming quadratic due to nested loops
• Counting 32^2 instead of 32

5. Suppose the input array can contain duplicate numbers and missing numbers may appear multiple times (i.e., numbers can be reused). Which modification to the XOR partitioning approach correctly finds the two missing numbers?

hard

A. Use frequency counting with a hash map instead of XOR to handle duplicates.

B. Use the same XOR partitioning approach since duplicates cancel out in XOR.

C. Modify XOR approach to XOR each number multiple times equal to its frequency.

D. Sort the array and scan for missing numbers instead of XOR.

Solution

1. Step 1: Understand impact of duplicates

   Duplicates break XOR approach because XOR assumes each number appears exactly once.

2. Step 2: Choose correct approach

   Frequency counting with a hash map correctly tracks counts and identifies missing numbers even with duplicates.

3. Step 3: Why other options fail

   Same XOR approach fails due to duplicates; modifying XOR by frequency is not feasible; sorting is O(n log n) and less efficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency counting handles duplicates correctly [OK]

Hint: XOR fails with duplicates; frequency map handles counts [OK]

Common Mistakes:

• Assuming XOR works with duplicates
• Trying to XOR multiple times per frequency
• Ignoring complexity of sorting