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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Construct Target Array With Multiple Sums

Number: 1479

Difficulty: Hard

Paid? No

Companies: Quora

Problem Description

Given an array target of n integers, determine if it is possible to construct target starting from an array arr of n ones. In each step, you can choose an index i and replace arr[i] with the sum of all elements in arr. Return true if the sequence of operations can convert arr to target, otherwise return false.

Key Insights

  • Instead of simulating the forward sum operations, work backwards from target.
  • The largest element in target must have been created by summing the rest of the array.
  • Use a maximum heap to efficiently extract the largest element.
  • At each step, let x be the maximum element and rest be the sum of all other elements.
  • The previous value of x must have been x % rest (if rest is not 1), since multiple operations may have been applied.
  • Edge cases include when rest is 0 or when x is less than or equal to rest.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of elements in target (each heap operation takes O(log n)). Space Complexity: O(n) for storing the heap.

Solution

The solution reverses the operation by always taking the largest element x from target and computing the hypothetical previous value before x was updated. The rest of the array has sum rest = total - x. If rest is 0 or x <= rest, we know that it's impossible to have reached the current state. Otherwise, compute new_x = x % rest. If new_x is 0, set new_x = rest. Update the total sum and push the new value back into the max-heap. Continue until every element reduces to 1 or until the operation is no longer possible.

Code Solutions

import heapq

class Solution:
    def isPossible(self, target):
        # Calculate the total sum of target
        total = sum(target)
        # Create a max heap using negative values (since Python's heapq is a min heap)
        target = [-x for x in target]
        heapq.heapify(target)
        
        # Continue until condition met
        while True:
            # Extract the largest element (convert from negative to positive)
            x = -heapq.heappop(target)
            rest = total - x
            # If the largest element is 1 or the rest of the array sums to 1, it is possible.
            if x == 1 or rest == 1:
                return True
            # If x is less than or equal to rest or rest is zero, transformation is impossible.
            if rest == 0 or x <= rest:
                return False
            # Determine the previous value for x using modulo (this step skips intermediate operations)
            new_x = x % rest
            # If new_x becomes 0, then assign it rest
            if new_x == 0:
                new_x = rest
            # Update the total sum with the new value
            total = rest + new_x
            # Push the updated value into the max heap (use negative for max heap simulation)
            heapq.heappush(target, -new_x)

# Example usage:
sol = Solution()
print(sol.isPossible([9, 3, 5]))  # Expected output: True
← Back to All Questions