Jobs

Interviews

Discussions

Count Pairs With XOR in a Range

Hard

Asked by:

12 views

Topics:

ArraysBit Manipulation

Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.

A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.

Example 1:

Input: nums = [1,4,2,7], low = 2, high = 6
Output: 6
Explanation: All nice pairs (i, j) are as follows:
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5

Example 2:

Input: nums = [9,8,4,2,1], low = 5, high = 14
Output: 8
Explanation: All nice pairs (i, j) are as follows:
    - (0, 2): nums[0] XOR nums[2] = 13
    - (0, 3): nums[0] XOR nums[3] = 11
    - (0, 4): nums[0] XOR nums[4] = 8
    - (1, 2): nums[1] XOR nums[2] = 12
    - (1, 3): nums[1] XOR nums[3] = 10
    - (1, 4): nums[1] XOR nums[4] = 9
    - (2, 3): nums[2] XOR nums[3] = 6
    - (2, 4): nums[2] XOR nums[4] = 5

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] <= 2 * 10⁴
1 <= low <= high <= 2 * 10⁴

Try coding it in LeetCode

Count Pairs With XOR in a Range

Hard

Asked by:

12 views

Topics:

ArraysBit Manipulation

Given a (0-indexed) integer array nums and two integers low and high, return the number of nice pairs.

A nice pair is a pair (i, j) where 0 <= i < j < nums.length and low <= (nums[i] XOR nums[j]) <= high.

Example 1:

Input: nums = [1,4,2,7], low = 2, high = 6
Output: 6
Explanation: All nice pairs (i, j) are as follows:
    - (0, 1): nums[0] XOR nums[1] = 5 
    - (0, 2): nums[0] XOR nums[2] = 3
    - (0, 3): nums[0] XOR nums[3] = 6
    - (1, 2): nums[1] XOR nums[2] = 6
    - (1, 3): nums[1] XOR nums[3] = 3
    - (2, 3): nums[2] XOR nums[3] = 5

Example 2:

Input: nums = [9,8,4,2,1], low = 5, high = 14
Output: 8
Explanation: All nice pairs (i, j) are as follows:
    - (0, 2): nums[0] XOR nums[2] = 13
    - (0, 3): nums[0] XOR nums[3] = 11
    - (0, 4): nums[0] XOR nums[4] = 8
    - (1, 2): nums[1] XOR nums[2] = 12
    - (1, 3): nums[1] XOR nums[3] = 10
    - (1, 4): nums[1] XOR nums[4] = 9
    - (2, 3): nums[2] XOR nums[3] = 6
    - (2, 4): nums[2] XOR nums[4] = 5

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i] <= 2 * 10⁴
1 <= low <= high <= 2 * 10⁴

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the inclusive bounds for the lower and upper limits of the XOR range, and are they integers?
What is the range of values for the numbers within the input array, and are they integers?
Can the input array contain duplicate numbers, and if so, should pairs (i, j) and (j, i) be counted as distinct if nums[i] == nums[j]?
Is the input array guaranteed to be non-empty, or should I handle the case where the array is null or empty?
If no pairs exist within the specified XOR range, what value should I return?

Brute Force Solution

Approach

The brute force way to solve this is to check every single possible pair of numbers we're given. For each pair, we'll calculate their XOR value and see if it falls within our specified range.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Compare it with every other number in the collection, one at a time.
For each pair, calculate their XOR value. Think of XOR as a special kind of addition.
Check if the resulting XOR value is greater than or equal to the lower bound of our range AND less than or equal to the upper bound of our range.
If it is, increase our count of pairs that meet the criteria by one.
Repeat this process, by taking the second number in the collection and comparing it to every number in the collection again.
Continue doing this for every number in the collection until we have considered all possible pairs.
The final count will represent the total number of pairs whose XOR value falls within our specified range.

Code Implementation

def count_xor_pairs_brute_force(
    numbers, lower_bound, upper_bound
):
    pair_count = 0

    # Iterate through each number in the list.
    for first_number_index in range(len(numbers)):
        for second_number_index in range(
            first_number_index + 1, len(numbers)
        ):
            # Calculating the XOR value is key to the problem.
            xor_result = (
                numbers[first_number_index]
                ^ numbers[second_number_index]
            )

            # Check if the XOR value falls within the specified range
            if (
                xor_result >= lower_bound
                and xor_result <= upper_bound
            ):
                # Increment the count if the XOR value is in range
                pair_count += 1

    return pair_count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n numbers in the input collection. Inside the outer loop, for each number, it compares it with every other number in the collection, resulting in another loop that runs up to n times. Each comparison involves calculating the XOR of the pair and checking if it falls within the range, both of which take constant time O(1). Therefore, we have approximately n * n operations. Simplifying n * n yields O(n²).

Space Complexity

O(1) – The provided brute force approach only uses a few integer variables: one for the first number's index, one for the second number's index, one to store the XOR result, and one to count the pairs. The number of these variables does not depend on the input size N (the number of elements in the collection). Thus, the auxiliary space used is constant.

Optimal Solution

Approach

The efficient strategy avoids checking every single pair of numbers. It smartly organizes and analyzes the numbers bit by bit to count the pairs that fit within the desired range.

Here's how the algorithm would work step-by-step:

Think of XOR as a way to compare numbers bit by bit and find their differences.
Imagine you have a special tool that can count how many numbers have a certain prefix of bits (like starting with '101').
Use this tool to count how many pairs XOR to something less than or equal to the upper limit of your range.
Do the same thing to count how many pairs XOR to something less than the lower limit of your range (the lower limit minus one).
Subtract the second count from the first count. This gives you the number of pairs that XOR to a value within your desired range.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = [None] * 2
        self.count = 0

class Solution:
    def countPairs(self, numbers: list[int], low_range: int, high_range: int) -> int:

        def get_count_less_than_or_equal_to(maximum_value: int) -> int:
            trie_root = TrieNode()
            count = 0

            def insert_number(number: int):
                current_node = trie_root
                for bit_index in range(15, -1, -1):
                    bit = (number >> bit_index) & 1
                    if not current_node.children[bit]:
                        current_node.children[bit] = TrieNode()
                    current_node = current_node.children[bit]
                    current_node.count += 1

            def find_pairs(number: int, max_xor: int) -> int:
                current_node = trie_root
                pair_count = 0
                for bit_index in range(15, -1, -1):
                    number_bit = (number >> bit_index) & 1
                    max_xor_bit = (max_xor >> bit_index) & 1

                    if max_xor_bit == 1:
                        #If current bit of max_xor is 1, explore the opposite bit.
                        if current_node.children[1 - number_bit]:
                            pair_count += current_node.children[1 - number_bit].count

                        # Move to the next bit in the same direction.
                        if not current_node.children[number_bit]:
                            return pair_count
                        current_node = current_node.children[number_bit]
                    else:
                        # If current bit of max_xor is 0, explore the same bit.
                        if not current_node.children[1 - number_bit]:
                            return pair_count
                        current_node = current_node.children[1 - number_bit]

                pair_count += current_node.count
                return pair_count

            for number in numbers:
                insert_number(number)

            for number in numbers:
                count += find_pairs(number, maximum_value)
            return count // 2

        # Calculating pairs within the high range.
        high_count = get_count_less_than_or_equal_to(high_range)

        # Calculating pairs less than the low range.
        low_count = get_count_less_than_or_equal_to(low_range - 1)

        # Subtract to find pairs within the specified range.
        return high_count - low_count

Big(O) Analysis

Time Complexity

O(n log(maxVal)) – The algorithm iterates through each number in the input array (size n). For each number, it traverses a binary tree-like structure whose depth is determined by the maximum value present in the input array, maxVal. The depth of this tree corresponds to the number of bits required to represent maxVal, which is log(maxVal). Therefore, for each of the n numbers, the algorithm performs operations proportional to log(maxVal). The total number of operations is then approximately n * log(maxVal), giving a time complexity of O(n log(maxVal)).

Space Complexity

O(1) – The provided strategy relies on a 'special tool' that counts numbers with a certain prefix of bits and uses this tool to perform subtractions. The plain english description does not mention any explicit auxiliary data structures like lists, hash maps, or recursion that depend on the input size N (where N is the number of elements). Thus, the space used remains constant regardless of the input size. The only space used is for a few variables to store intermediate counts, which is independent of N.

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return 0 to indicate invalid input
Array with fewer than 2 elements	Return 0 because a pair cannot be formed
Lower bound greater than upper bound	Return 0 because the range is invalid
Large array with a wide range of values leading to potential integer overflow in XOR operation	Use a data type with sufficient capacity (e.g., long) to store the XOR result, or check before operations to prevent overflow
Array contains negative numbers	Ensure the XOR operation and range comparison handle negative values correctly; negative XOR results are valid
Lower bound and upper bound are both zero	Count pairs with XOR equal to 0, which typically means counting pairs of identical numbers
All elements in the array are identical	Efficiently calculate the number of pairs using combinatorics n*(n-1)/2 where n is number of elements
Extreme boundary values for array elements or target range (close to max int)	Be cautious of potential integer overflow during XOR or range comparison operations; consider using larger data types

Null input array

How to Handle:

Throw an IllegalArgumentException or return 0 to indicate invalid input

Array with fewer than 2 elements

How to Handle:

Return 0 because a pair cannot be formed

Lower bound greater than upper bound

How to Handle:

Return 0 because the range is invalid

Large array with a wide range of values leading to potential integer overflow in XOR operation

How to Handle:

Use a data type with sufficient capacity (e.g., long) to store the XOR result, or check before operations to prevent overflow

Array contains negative numbers

How to Handle:

Ensure the XOR operation and range comparison handle negative values correctly; negative XOR results are valid

Lower bound and upper bound are both zero

How to Handle:

Count pairs with XOR equal to 0, which typically means counting pairs of identical numbers

All elements in the array are identical

How to Handle:

Efficiently calculate the number of pairs using combinatorics n*(n-1)/2 where n is number of elements

Extreme boundary values for array elements or target range (close to max int)

How to Handle:

Be cautious of potential integer overflow during XOR or range comparison operations; consider using larger data types

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the inclusive bounds for the lower and upper limits of the XOR range, and are they integers?
What is the range of values for the numbers within the input array, and are they integers?
Can the input array contain duplicate numbers, and if so, should pairs (i, j) and (j, i) be counted as distinct if nums[i] == nums[j]?
Is the input array guaranteed to be non-empty, or should I handle the case where the array is null or empty?
If no pairs exist within the specified XOR range, what value should I return?

Brute Force Solution

Approach

The brute force way to solve this is to check every single possible pair of numbers we're given. For each pair, we'll calculate their XOR value and see if it falls within our specified range.

Here's how the algorithm would work step-by-step:

Take the first number in the collection.
Compare it with every other number in the collection, one at a time.
For each pair, calculate their XOR value. Think of XOR as a special kind of addition.
Check if the resulting XOR value is greater than or equal to the lower bound of our range AND less than or equal to the upper bound of our range.
If it is, increase our count of pairs that meet the criteria by one.
Repeat this process, by taking the second number in the collection and comparing it to every number in the collection again.
Continue doing this for every number in the collection until we have considered all possible pairs.
The final count will represent the total number of pairs whose XOR value falls within our specified range.

Code Implementation

def count_xor_pairs_brute_force(
    numbers, lower_bound, upper_bound
):
    pair_count = 0

    # Iterate through each number in the list.
    for first_number_index in range(len(numbers)):
        for second_number_index in range(
            first_number_index + 1, len(numbers)
        ):
            # Calculating the XOR value is key to the problem.
            xor_result = (
                numbers[first_number_index]
                ^ numbers[second_number_index]
            )

            # Check if the XOR value falls within the specified range
            if (
                xor_result >= lower_bound
                and xor_result <= upper_bound
            ):
                # Increment the count if the XOR value is in range
                pair_count += 1

    return pair_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The efficient strategy avoids checking every single pair of numbers. It smartly organizes and analyzes the numbers bit by bit to count the pairs that fit within the desired range.

Here's how the algorithm would work step-by-step:

Think of XOR as a way to compare numbers bit by bit and find their differences.
Imagine you have a special tool that can count how many numbers have a certain prefix of bits (like starting with '101').
Use this tool to count how many pairs XOR to something less than or equal to the upper limit of your range.
Do the same thing to count how many pairs XOR to something less than the lower limit of your range (the lower limit minus one).
Subtract the second count from the first count. This gives you the number of pairs that XOR to a value within your desired range.

Code Implementation

class TrieNode:
    def __init__(self):
        self.children = [None] * 2
        self.count = 0

class Solution:
    def countPairs(self, numbers: list[int], low_range: int, high_range: int) -> int:

        def get_count_less_than_or_equal_to(maximum_value: int) -> int:
            trie_root = TrieNode()
            count = 0

            def insert_number(number: int):
                current_node = trie_root
                for bit_index in range(15, -1, -1):
                    bit = (number >> bit_index) & 1
                    if not current_node.children[bit]:
                        current_node.children[bit] = TrieNode()
                    current_node = current_node.children[bit]
                    current_node.count += 1

            def find_pairs(number: int, max_xor: int) -> int:
                current_node = trie_root
                pair_count = 0
                for bit_index in range(15, -1, -1):
                    number_bit = (number >> bit_index) & 1
                    max_xor_bit = (max_xor >> bit_index) & 1

                    if max_xor_bit == 1:
                        #If current bit of max_xor is 1, explore the opposite bit.
                        if current_node.children[1 - number_bit]:
                            pair_count += current_node.children[1 - number_bit].count

                        # Move to the next bit in the same direction.
                        if not current_node.children[number_bit]:
                            return pair_count
                        current_node = current_node.children[number_bit]
                    else:
                        # If current bit of max_xor is 0, explore the same bit.
                        if not current_node.children[1 - number_bit]:
                            return pair_count
                        current_node = current_node.children[1 - number_bit]

                pair_count += current_node.count
                return pair_count

            for number in numbers:
                insert_number(number)

            for number in numbers:
                count += find_pairs(number, maximum_value)
            return count // 2

        # Calculating pairs within the high range.
        high_count = get_count_less_than_or_equal_to(high_range)

        # Calculating pairs less than the low range.
        low_count = get_count_less_than_or_equal_to(low_range - 1)

        # Subtract to find pairs within the specified range.
        return high_count - low_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null input array	Throw an IllegalArgumentException or return 0 to indicate invalid input
Array with fewer than 2 elements	Return 0 because a pair cannot be formed
Lower bound greater than upper bound	Return 0 because the range is invalid
Large array with a wide range of values leading to potential integer overflow in XOR operation	Use a data type with sufficient capacity (e.g., long) to store the XOR result, or check before operations to prevent overflow
Array contains negative numbers	Ensure the XOR operation and range comparison handle negative values correctly; negative XOR results are valid
Lower bound and upper bound are both zero	Count pairs with XOR equal to 0, which typically means counting pairs of identical numbers
All elements in the array are identical	Efficiently calculate the number of pairs using combinatorics n*(n-1)/2 where n is number of elements
Extreme boundary values for array elements or target range (close to max int)	Be cautious of potential integer overflow during XOR or range comparison operations; consider using larger data types

Null input array

How to Handle:

Throw an IllegalArgumentException or return 0 to indicate invalid input

Array with fewer than 2 elements

How to Handle:

Return 0 because a pair cannot be formed

Lower bound greater than upper bound

How to Handle:

Return 0 because the range is invalid

Large array with a wide range of values leading to potential integer overflow in XOR operation

How to Handle:

Use a data type with sufficient capacity (e.g., long) to store the XOR result, or check before operations to prevent overflow

Array contains negative numbers

How to Handle:

Ensure the XOR operation and range comparison handle negative values correctly; negative XOR results are valid

Lower bound and upper bound are both zero

How to Handle:

Count pairs with XOR equal to 0, which typically means counting pairs of identical numbers

All elements in the array are identical

How to Handle:

Efficiently calculate the number of pairs using combinatorics n*(n-1)/2 where n is number of elements

Extreme boundary values for array elements or target range (close to max int)

How to Handle:

Be cautious of potential integer overflow during XOR or range comparison operations; consider using larger data types