Choose Numbers From Two Arrays in Range - Practice Coding Problems

Choose Numbers From Two Arrays in Range - Problem

You are given two 0-indexed integer arrays nums1 and nums2 of length n.

A range [l, r] (inclusive) where 0 <= l <= r < n is balanced if:

For every i in the range [l, r], you pick either nums1[i] or nums2[i].
The sum of the numbers you pick from nums1 equals the sum of the numbers you pick from nums2 (the sum is considered to be 0 if you pick no numbers from an array).

Two balanced ranges [l1, r1] and [l2, r2] are considered to be different if at least one of the following is true:

l1 != l2
r1 != r2
nums1[i] is picked in the first range, and nums2[i] is picked in the second range or vice versa for at least one i.

Return the number of different ranges that are balanced. Since the answer may be very large, return it modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [1,2,3], nums2 = [4,5,6]

› Output: 4

💡 Note: Range [0,0]: pick nums1[0]=1 or nums2[0]=4, no balance. Range [1,1]: pick nums1[1]=2 or nums2[1]=5, no balance. Range [2,2]: pick nums1[2]=3 or nums2[2]=6, no balance. Range [0,1]: selections (nums2[0],nums1[1])=(4,2) sum1=2,sum2=4; (nums1[0],nums2[1])=(1,5) sum1=1,sum2=5; no balance for other selections. Continue checking all ranges - total balanced ranges is 4.

Example 2 — Equal Arrays

$ Input: nums1 = [1,1], nums2 = [1,1]

› Output: 6

💡 Note: Since arrays are identical, each range has balanced selections: Range [0,0]: 1 way (pick either). Range [1,1]: 1 way. Range [0,1]: 4 ways since all selections give equal sums.

Example 3 — Single Element

$ Input: nums1 = [5], nums2 = [5]

› Output: 2

💡 Note: Only one range [0,0]. Two selections: pick nums1[0]=5 (sum1=5, sum2=0) or nums2[0]=5 (sum1=0, sum2=5). Neither is balanced, but the problem counts different ways to make selections, giving us 2.

Constraints

1 ≤ n ≤ 100
-1000 ≤ nums1[i], nums2[i] ≤ 1000
Answer fits in 32-bit integer after modulo

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays nums1 and nums2 of equal length

Process

For each range [l,r], count ways to select nums1[i] or nums2[i] such that sums are equal

Output

Total count of different balanced ranges modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Transform to difference array and use DP to count zero-sum selections efficiently

Asked in

G Google 15 f Meta 12 a Amazon 8

The key insight is to transform the problem by creating a difference array diff[i] = nums1[i] - nums2[i], then use dynamic programming to count ways to achieve sum = 0 for each range. Best approach uses space-optimized DP with Time: O(n² × S), Space: O(S) where S is the sum range.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Ranges and Selections	O(n² × 2ⁿ)	O(1)	Generate every possible range and every possible selection, count balanced ones
Optimized DP with Difference Array	O(n² × S)	O(S)	Transform arrays into difference array and use space-optimized DP
Dynamic Programming with Memoization	O(n² × S)	O(n × S)	Use memoization to avoid recomputing the same subproblems for different ranges

Brute Force - Try All Ranges and Selections — Algorithm Steps

Step 1: Iterate through all possible ranges [l,r] where 0 <= l <= r < n
Step 2: For each range, generate all 2^(range_size) possible selections using bit manipulation
Step 3: For each selection, calculate sum from nums1 and nums2, check if equal
Step 4: Count all balanced selections and return total modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Ranges

Try all [l,r] ranges

Generate Selections

For each range, try all 2^k ways to pick

Count Balanced

Count selections where sum1 = sum2

Code -

solution.c — C

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

int solution(int* nums1, int* nums2, int n) {
    const int MOD = 1000000007;
    int result = 0;
    
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int rangeSize = r - l + 1;
            // Try all 2^rangeSize selections
            for (int mask = 0; mask < (1 << rangeSize); mask++) {
                int sum1 = 0, sum2 = 0;
                for (int i = 0; i < rangeSize; i++) {
                    if (mask & (1 << i)) {
                        sum1 += nums1[l + i];
                    } else {
                        sum2 += nums2[l + i];
                    }
                }
                if (sum1 == sum2) {
                    result = (result + 1) % MOD;
                }
            }
        }
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int nums1[100], n1 = 0;
    char* token = strtok(line, "[,]");
    while (token) {
        if (token[0] >= '0' || token[0] == '-') {
            nums1[n1++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    int nums2[100], n2 = 0;
    token = strtok(line, "[,]");
    while (token) {
        if (token[0] >= '0' || token[0] == '-') {
            nums2[n2++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums1, nums2, n1));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² × 2ⁿ)

O(n²) ranges, each with O(2^n) selections to check in worst case

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 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 - Try All Ranges and Selections — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler