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: 0

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

Example 2 — Single Element

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

› Output: 1

💡 Note: We can choose l = 2 and r = 3. func(arr, 2, 3) = 3 ⊕ 7 = 4. |4 - 5| = 1. This gives the minimum difference of 1.

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

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

✓ Hash Map

⏱️ Time: N/A Space: N/A

Advanced - Trie with Binary Search

⏱️ Time: O(n² + 20) Space: O(n² * 20)

Build a trie (prefix tree) to store all possible XOR values from subarrays. Then for each XOR value, use the trie structure to efficiently find the closest match to target using binary search principles.

Brute Force - Try All Subarrays

⏱️ Time: O(n³) Space: O(1)

Generate all possible subarrays by trying every combination of left and right indices. For each subarray, calculate the XOR of all elements and find the absolute difference with target.

Optimized - Incremental XOR

⏱️ Time: O(n²) Space: O(1)

Instead of recalculating XOR for each subarray from scratch, we can build XOR results incrementally. For a fixed left index, we extend the right index and update XOR incrementally.

Algorithm Steps — Algorithm Steps

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 minDiff = INT_MAX;
    
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int xorResult = 0;
            for (int i = l; i <= r; i++) {
                xorResult ^= arr[i];
            }
            int diff = abs(xorResult - target);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
    }
    
    return minDiff;
}

int parseArray(const char* str, int* arr) {
    int size = 0;
    const char* p = str;
    
    // Skip to first '['
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        
        char* endptr;
        arr[size++] = (int)strtol(p, &endptr, 10);
        p = endptr;
    }
    
    return size;
}

int main() {
    char line[10000];
    int arr[1000];
    
    // Read array
    fgets(line, sizeof(line), stdin);
    int n = parseArray(line, arr);
    
    // Read target
    fgets(line, sizeof(line), stdin);
    int target = atoi(line);
    
    int result = solution(arr, n, target);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

⚠ Quadratic Growth

Space Complexity

⚠ 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