Count Pairs With XOR in a Range - Practice Coding Problems

Count Pairs With XOR in a Range - Problem

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
low <= (nums[i] XOR nums[j]) <= high

The XOR operation computes the bitwise exclusive OR of two numbers.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,4,2,7], low = 1, high = 4

› Output: 2

💡 Note: Nice pairs are (0,2): 1^2=3 ∈ [1,4] and (1,3): 4^7=3 ∈ [1,4]. Total count is 2.

Example 2 — Wider Range

$ Input: nums = [9,8,4,2,1], low = 5, high = 14

› Output: 8

💡 Note: Multiple pairs have XOR values in [5,14]: (0,1): 9^8=1 ✗, (0,2): 9^4=13 ✓, (0,3): 9^2=11 ✓, etc. Count all valid pairs.

Example 3 — No Valid Pairs

$ Input: nums = [1,1,1], low = 5, high = 10

› Output: 0

💡 Note: All pairs have XOR = 1^1 = 0, which is not in range [5,10]. No nice pairs exist.

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 2 × 10⁴
1 ≤ low ≤ high ≤ 2 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[1,4,2,7] and range [1,4]

Find Pairs

Check all pairs (i,j) where i<j for XOR in range

Count Valid

Count pairs with XOR ∈ [1,4]: result is 2

Key Takeaway

🎯 Key Insight: Use trie data structure to efficiently count XOR values in ranges without checking all pairs

Asked in

G Google 35 a Amazon 28 M Microsoft 22

The key insight is that we need to count pairs efficiently where XOR falls in a range. The brute force approach checks all pairs in O(n²) time. The optimal trie-based solution uses binary representation to count XOR values in range efficiently. Time: O(n × log(max_val)), Space: O(n × log(max_val))

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Pairs	O(n²)	O(1)	Check every possible pair (i,j) and count those with XOR in range
Trie-Based XOR Range Count	O(n × log(max_val))	O(n × log(max_val))	Use trie data structure to efficiently count XOR values in range

Brute Force - Check All Pairs — Algorithm Steps

Iterate through all pairs (i,j) where i < j
Calculate nums[i] XOR nums[j]
Check if XOR value is between low and high
Count valid pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Pairs

Create all pairs (i,j) with i < j

Compute XOR

Calculate nums[i] ^ nums[j] for each pair

Count Valid

Count pairs where XOR is in [low, high]

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int low, int high) {
    int count = 0;
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            int xorVal = nums[i] ^ nums[j];
            if (low <= xorVal && xorVal <= high) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int low, high;
    scanf("%d", &low);
    scanf("%d", &high);
    
    int result = solution(nums, numsSize, low, high);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops check all n*(n-1)/2 pairs

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

38.5K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler