Construct Target Array With Multiple Sums

Construct Target Array With Multiple Sums - Problem

You are given an array target of n integers. From a starting array arr consisting of n 1's, you may perform the following procedure:

Let x be the sum of all elements currently in your array.
Choose index i, such that 0 <= i < n and set the value of arr at index i to x.

You may repeat this procedure as many times as needed.

Return true if it is possible to construct the target array from arr, otherwise, return false.

Input & Output

Example 1 — Basic Possible Case

$ Input: target = [9,3,5]

› Output: true

💡 Note: Starting from [1,1,1]: Replace index 0 with sum=3 → [3,1,1], then replace index 2 with sum=5 → [3,1,5], finally replace index 0 with sum=9 → [9,3,5]. Working backwards confirms this is possible.

Example 2 — Impossible Case

$ Input: target = [1,1,1,2]

› Output: false

💡 Note: The sum is 5. For 2 to be created, the previous sum must have been 2, but that would require other elements to sum to 0, which is impossible since all elements must be positive.

Example 3 — Single Element

$ Input: target = [8]

› Output: true

💡 Note: Single element case: start with [1], replace with 1 → [1], replace with 1 → [1], ..., eventually we can build up to any positive integer.

Constraints

1 ≤ target.length ≤ 5 × 10⁴
1 ≤ target[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Start

Begin with array [1,1,1]

Transform

Replace elements with current sum

Target

Check if we can reach target [9,3,5]

Key Takeaway

🎯 Key Insight: Work backwards from the target - the largest element reveals the previous state

Asked in

G Google 15 a Amazon 12 f Facebook 8

The key insight is to work backwards from the target array. The largest element must have been created by replacing some previous element with the sum of all elements. Using a max heap to efficiently process the largest elements, we can reverse-engineer the construction process. Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Forward Simulation (Brute Force)	O(2^n)	O(2^n)	Try all possible sequences of operations starting from [1,1,...,1]
Reverse Engineering with Max Heap	O(n log n)	O(n)	Work backwards from target using heap to process largest elements first

Forward Simulation (Brute Force) — Algorithm Steps

Start with array of all 1's
Try replacing each element with current sum
Recursively continue until target found or impossible

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with array [1,1,1]

Branch

Try replacing each position with sum

Explore

Recursively try all possibilities

Code -

solution.c — C

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

bool backtrack(int* arr, int* target, int n) {
    // Check equality
    bool equal = true;
    for (int i = 0; i < n; i++) {
        if (arr[i] != target[i]) {
            equal = false;
            break;
        }
    }
    if (equal) return true;
    
    // Pruning
    for (int i = 0; i < n; i++) {
        if (arr[i] > target[i]) {
            return false;
        }
    }
    
    int currentSum = 0;
    for (int i = 0; i < n; i++) {
        currentSum += arr[i];
    }
    
    for (int i = 0; i < n; i++) {
        if (arr[i] < target[i]) {
            int* newArr = (int*)malloc(n * sizeof(int));
            memcpy(newArr, arr, n * sizeof(int));
            newArr[i] = currentSum;
            bool result = backtrack(newArr, target, n);
            free(newArr);
            if (result) return true;
        }
    }
    
    return false;
}

bool solution(int* target, int n) {
    if (n == 1) {
        return target[0] >= 1;
    }
    
    int* start = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        start[i] = 1;
    }
    
    bool result = backtrack(start, target, n);
    free(start);
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array
    int target[100];
    int n = 0;
    char* token = strtok(line, "[,] \n");
    while (token != NULL) {
        target[n++] = atoi(token);
        token = strtok(NULL, "[,] \n");
    }
    
    bool result = solution(target, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Exponential branches as each position can be updated multiple times

⚠ Quadratic Growth

Space Complexity

O(2^n)

Recursion stack and visited states grow exponentially

⚠ Quadratic Space

32.0K Views

Medium Frequency

~25 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

Forward Simulation (Brute Force) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler