Partition Array to Minimize XOR - Practice Coding Problems

Partition Array to Minimize XOR - Problem

You are given an integer array nums and an integer k. Your task is to partition nums into k non-empty subarrays.

For each subarray, compute the bitwise XOR of all its elements. Return the minimum possible value of the maximum XOR among these k subarrays.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4], k = 2

› Output: 4

💡 Note: Optimal partition: [1,2,3] with XOR = 0, and [4] with XOR = 4. Maximum XOR = max(0,4) = 4.

Example 2 — Single Elements

$ Input: nums = [5,6,7], k = 3

› Output: 7

💡 Note: Each element forms its own partition: [5], [6], [7]. Maximum XOR = max(5,6,7) = 7.

Example 3 — All Together

$ Input: nums = [1,1,1,1], k = 1

› Output: 0

💡 Note: All elements in one partition: [1,1,1,1]. XOR = 1⊕1⊕1⊕1 = 0.

Constraints

1 ≤ nums.length ≤ 10³
1 ≤ nums[i] ≤ 10⁶
1 ≤ k ≤ nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,4] with k=2 partitions needed

Process

Try different ways to partition and compute XOR for each part

Output

Return minimum possible maximum XOR value: 4

Key Takeaway

🎯 Key Insight: Binary search on the answer space (maximum XOR values) with greedy feasibility checking

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is to use binary search on the maximum XOR value. We search between 0 and the maximum possible XOR, then for each candidate maximum, greedily check if we can form k partitions where no partition's XOR exceeds the candidate. Best approach is Binary Search on Answer with greedy validation. Time: O(n × log(maxXOR)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n² × k)	O(n × k)	Cache results of subproblems to avoid recomputation
Binary Search on Answer	O(n × log(maxXOR))	O(1)	Binary search on the maximum XOR value and check feasibility
Brute Force Recursion	O(2^n)	O(n)	Try all possible ways to partition the array into k subarrays

Dynamic Programming with Memoization — Algorithm Steps

Use recursion with memoization
Cache results by (index, parts_left)
Compute XOR incrementally
Return cached result if available

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Before computing, check if result already exists

Compute & Store

If not cached, compute result and store in memo table

Reuse Results

Later identical subproblems use cached results

Code -

solution.c — C

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

typedef struct {
    int idx;
    int partsLeft;
    int result;
} MemoEntry;

MemoEntry memo[10000];
int memoSize = 0;

int findMemo(int idx, int partsLeft) {
    for (int i = 0; i < memoSize; i++) {
        if (memo[i].idx == idx && memo[i].partsLeft == partsLeft) {
            return memo[i].result;
        }
    }
    return -1;
}

void addMemo(int idx, int partsLeft, int result) {
    if (memoSize < 10000) {
        memo[memoSize].idx = idx;
        memo[memoSize].partsLeft = partsLeft;
        memo[memoSize].result = result;
        memoSize++;
    }
}

int solve(int* nums, int n, int idx, int partsLeft) {
    int cached = findMemo(idx, partsLeft);
    if (cached != -1) return cached;
    
    if (partsLeft == 1) {
        int xorVal = 0;
        for (int i = idx; i < n; i++) {
            xorVal ^= nums[i];
        }
        addMemo(idx, partsLeft, xorVal);
        return xorVal;
    }
    
    if (idx >= n || partsLeft <= 0) {
        addMemo(idx, partsLeft, INT_MAX);
        return INT_MAX;
    }
    
    int minMaxXor = INT_MAX;
    int currentXor = 0;
    
    for (int end = idx; end <= n - partsLeft; end++) {
        currentXor ^= nums[end];
        int remainingMax = solve(nums, n, end + 1, partsLeft - 1);
        if (remainingMax != INT_MAX) {
            int currentMax = (currentXor > remainingMax) ? currentXor : remainingMax;
            minMaxXor = (minMaxXor < currentMax) ? minMaxXor : currentMax;
        }
    }
    
    addMemo(idx, partsLeft, minMaxXor);
    return minMaxXor;
}

int solution(int* nums, int numsSize, int k) {
    memoSize = 0;
    return solve(nums, numsSize, 0, k);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n² × k)

At most n×k states, each taking O(n) time to compute all partition points

⚠ Quadratic Growth

Space Complexity

O(n × k)

Memoization table stores results for n×k states plus recursion stack

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

234 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

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler