We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Construct Target Array With Multiple Sums

Difficulty: Hard

Problem Description

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.

Key Insights

  • The sum of the target array must be greater than or equal to the sum of the initial array, which consists of all 1's.
  • Each element in the target array must be achievable through the sum of the elements in the current array.
  • The maximum element in the target array should not exceed the sum of the other elements plus one, to ensure that we can reduce the maximum element back to form the other values.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

To determine if we can construct the target array from the starting array of ones, we can use a max-heap (or priority queue). The algorithm follows these steps:

  1. Calculate the total sum of the target array.
  2. Push all elements of the target array into a max-heap.
  3. While the maximum element of the heap is greater than 1, perform the following:
    • Extract the maximum element.
    • Calculate the new value by subtracting the sum of the other elements (total sum - max element).
    • If the new value is valid (greater than 0 and less than the maximum), push it back into the heap.
  4. If we can continue this process without contradiction, return true; otherwise, return false.

Code Solutions

import heapq

def isPossible(target):
    total_sum = sum(target)
    max_heap = [-x for x in target]  # use negative to simulate max-heap
    heapq.heapify(max_heap)

    while True:
        max_val = -heapq.heappop(max_heap)  # get the maximum value
        total_sum -= max_val  # subtract it from the total sum

        if max_val == 1 or total_sum == 1:  # base case
            return True

        if total_sum <= 0 or max_val <= total_sum:  # not possible
            return False
        
        # New value we want to push back is max_val - total_sum
        new_val = max_val % total_sum
        if new_val == 0 or new_val == max_val:  # if it doesn't change
            return False
        
        total_sum += new_val  # update total sum
        heapq.heappush(max_heap, -new_val)  # push back the new value
← Back to All Questions