Minimum Sum of Values by Dividing Array - Practice Coding Problems

Minimum Sum of Values by Dividing Array - Problem

Array Binary Search Dynamic Programming Bit Manipulation Segment Tree Queue Hard

You are given two arrays nums and andValues of length n and m respectively.

The value of an array is equal to the last element of that array.

You have to divide nums into m disjoint contiguous subarrays such that for the i-th subarray [l_i, r_i], the bitwise AND of the subarray elements is equal to andValues[i].

In other words: nums[l_i] & nums[l_i + 1] & ... & nums[r_i] == andValues[i] for all 1 <= i <= m, where & represents the bitwise AND operator.

Return the minimum possible sum of the values of the m subarrays nums is divided into. If it is not possible to divide nums into m subarrays satisfying these conditions, return -1.

Input & Output

Example 1 — Basic Case

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

› Output: 12

💡 Note: Divide into [1,4], [3], [3], [2]. AND values: 1&4=0, 3=3, 3=3, 2=2. Sum of last elements: 4+3+3+2=12.

Example 2 — Impossible Case

$ Input: nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

› Output: -1

💡 Note: Cannot divide array into 3 subarrays with required AND values.

Example 3 — Single Elements

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

› Output: -1

💡 Note: No single subarray can have AND value of 2 from these elements.

Constraints

1 ≤ n == nums.length ≤ 10⁴
1 ≤ m == andValues.length ≤ min(n, 10)
1 ≤ nums[i] < 10⁵
0 ≤ andValues[i] < 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,4,3,3,2] and AND values [0,3,3,2]

Process

Find valid divisions where each subarray AND matches required value

Output

Minimum sum of last elements: 12

Key Takeaway

🎯 Key Insight: Use DP to try all valid divisions where subarray AND values match requirements

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is to use dynamic programming with memoization to explore all valid array divisions efficiently. The AND operation has the property that it can only decrease or stay the same as we extend a subarray. Best approach is memoization with state (index, group, current_and). Time: O(n × m × 2^20), Space: O(n × m × 2^20)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n × m × 2^20)	O(n × m × 2^20)	Cache results to avoid recalculating same subproblems
Brute Force Recursion	O(2^n)	O(n)	Try all possible ways to divide the array into m subarrays

Dynamic Programming with Memoization — Algorithm Steps

Define state as (index, group, current_and)
Check memo table before calculating
Calculate result recursively if not cached
Store result in memo table before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Cache

Look up (index, group, AND) in memo table

Calculate

If not found, compute result recursively

Store

Cache result for future use

Code -

solution.c — C

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

typedef struct {
    char key[100];
    int value;
} MemoEntry;

MemoEntry memo[100000];
int memoSize = 0;

int getMemo(int idx, int group, int currentAnd) {
    char key[100];
    sprintf(key, "%d,%d,%d", idx, group, currentAnd);
    for (int i = 0; i < memoSize; i++) {
        if (strcmp(memo[i].key, key) == 0) {
            return memo[i].value;
        }
    }
    return -1;
}

void setMemo(int idx, int group, int currentAnd, int value) {
    char key[100];
    sprintf(key, "%d,%d,%d", idx, group, currentAnd);
    strcpy(memo[memoSize].key, key);
    memo[memoSize].value = value;
    memoSize++;
}

int solve(int* nums, int numsSize, int* andValues, int andValuesSize, int idx, int group, int currentAnd) {
    int memoResult = getMemo(idx, group, currentAnd);
    if (memoResult != -1) {
        return memoResult;
    }
    
    // Base cases
    if (group == andValuesSize) {
        int result = idx == numsSize ? 0 : INT_MAX;
        setMemo(idx, group, currentAnd, result);
        return result;
    }
    if (idx >= numsSize) {
        setMemo(idx, group, currentAnd, INT_MAX);
        return INT_MAX;
    }
    
    int minSum = INT_MAX;
    currentAnd &= nums[idx];
    
    // Try ending current subarray here
    if (currentAnd == andValues[group]) {
        int rest = solve(nums, numsSize, andValues, andValuesSize, idx + 1, group + 1, (1 << 20) - 1);
        if (rest != INT_MAX) {
            minSum = (nums[idx] + rest < minSum) ? nums[idx] + rest : minSum;
        }
    }
    
    // Try extending current subarray
    int extend = solve(nums, numsSize, andValues, andValuesSize, idx + 1, group, currentAnd);
    minSum = (extend < minSum) ? extend : minSum;
    
    setMemo(idx, group, currentAnd, minSum);
    return minSum;
}

int solution(int* nums, int numsSize, int* andValues, int andValuesSize) {
    memoSize = 0;
    int result = solve(nums, numsSize, andValues, andValuesSize, 0, 0, (1 << 20) - 1);
    return result == INT_MAX ? -1 : result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int nums[100], numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    // Parse second array
    int andValues[100], andValuesSize = 0;
    token = strtok(line + 1, ",]");
    while (token != NULL) {
        andValues[andValuesSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, numsSize, andValues, andValuesSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × 2^20)

We have n positions, m groups, and up to 2^20 possible AND values to memoize

✓ Linear Growth

Space Complexity

O(n × m × 2^20)

Memoization table stores results for all possible states plus recursion stack

⚡ Linearithmic Space

12.0K 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