Find a Value of a Mysterious Function Closest to Target

Find a Value of a Mysterious Function Closest to Target - Problem

You are given an integer array arr and an integer target. You need to find the values l and r such that 0 <= l, r < arr.length that make the value |func(arr, l, r) - target| minimum possible.

The mysterious function func(arr, l, r) returns the bitwise XOR of all elements in the subarray from index l to index r (inclusive).

Return the minimum possible value of |func(arr, l, r) - target|.

Input & Output

Example 1 — Basic Case

$ Input: arr = [1,2,3,4], target = 6

› Output: 1

💡 Note: We can choose l = 1 and r = 2. func(arr, 1, 2) = 2 ⊕ 3 = 1. |1 - 6| = 5. We can also choose l = 2 and r = 3. func(arr, 2, 3) = 3 ⊕ 4 = 7. |7 - 6| = 1. The minimum is 1.

Example 2 — Single Element

$ Input: arr = [9,12,3,7,15], target = 5

› Output: 2

💡 Note: We can choose l = 3 and r = 3. func(arr, 3, 3) = 7. |7 - 5| = 2. We can also try other subarrays but this gives the minimum difference of 2.

Example 3 — Target Match

$ Input: arr = [4,6,7,9], target = 6

› Output: 0

💡 Note: We can choose l = 1 and r = 1. func(arr, 1, 1) = 6. |6 - 6| = 0. Perfect match!

Constraints

1 ≤ arr.length ≤ 10⁵
0 ≤ arr[i] ≤ 10⁸
0 ≤ target ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,4] and target = 6

Process

Calculate XOR for all subarrays

Output

Return minimum |XOR - target|

Key Takeaway

🎯 Key Insight: XOR has unique properties - we need to check all possible subarrays to find the one with XOR value closest to target

Asked in

G Google 45 f Facebook 32 M Microsoft 28

The key insight is to efficiently generate all possible subarray XOR values and find the one closest to target. The optimized approach uses incremental XOR calculation to avoid redundant computations, achieving O(n²) time complexity. Best approach: Incremental XOR - Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Advanced - Trie with Binary Search	O(n² + 20)	O(n² * 20)	Use trie to store XOR values and binary search for closest match
Brute Force - Try All Subarrays	O(n³)	O(1)	Calculate XOR for every possible subarray and find minimum difference
Optimized - Incremental XOR	O(n²)	O(1)	Build XOR results incrementally to avoid recalculating from scratch

Advanced - Trie with Binary Search — Algorithm Steps

Generate all subarray XOR values using incremental approach
Store XOR values in a trie data structure
For target, traverse trie to find closest XOR value
Use bit manipulation to guide search direction

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate XOR Values

Calculate all possible subarray XORs

Store in Set

Eliminate duplicate XOR values

Find Closest

Check each unique XOR against target

Code -

solution.c — C

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

int solution(int* arr, int n, int target) {
    int xorValues[10000];
    int valueCount = 0;
    
    for (int l = 0; l < n; l++) {
        int xorResult = 0;
        for (int r = l; r < n; r++) {
            xorResult ^= arr[r];
            // Check if already exists
            int exists = 0;
            for (int i = 0; i < valueCount; i++) {
                if (xorValues[i] == xorResult) {
                    exists = 1;
                    break;
                }
            }
            if (!exists) {
                xorValues[valueCount++] = xorResult;
            }
        }
    }
    
    int minDiff = INT_MAX;
    for (int i = 0; i < valueCount; i++) {
        int diff = abs(xorValues[i] - target);
        if (diff < minDiff) {
            minDiff = diff;
        }
    }
    
    return minDiff;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        arr[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int target;
    scanf("%d", &target);
    
    int result = solution(arr, n, target);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² + 20)

O(n²) to generate all XOR values, O(20) to search trie (assuming 20-bit integers)

⚠ Quadratic Growth

Space Complexity

O(n² * 20)

Trie can store up to n² XOR values, each requiring up to 20 nodes

⚠ Quadratic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 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

Advanced - Trie with Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler