1354. Construct Target Array With Multiple Sums LeetCode Solution

In this guide, you will get 1354. Construct Target Array With Multiple Sums LeetCode Solution with the best time and space complexity. The solution to Construct Target Array With Multiple Sums problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Construct Target Array With Multiple Sums solution in C++
Construct Target Array With Multiple Sums solution in Java
Construct Target Array With Multiple Sums solution in Python
Additional Resources

1354. Construct Target Array With Multiple Sums LeetCode Solution image

Problem Statement of Construct Target Array With Multiple Sums

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.

Example 1:

Input: target = [9,3,5]
Output: true
Explanation: Start with arr = [1, 1, 1]
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done

Example 2:

Input: target = [1,1,1,2]
Output: false
Explanation: Impossible to create target array from [1,1,1,1].

Example 3:

Input: target = [8,5]
Output: true

Constraints:

n == target.length
1 <= n <= 5 * 104
1 <= target[i] <= 109

Complexity Analysis

Time Complexity: O(n + \log(\Sigma |\texttt{target[i]}|) \cdot \log n)
Space Complexity: O(n)

1354. Construct Target Array With Multiple Sums LeetCode Solution in C++

class Solution {
 public:
  bool isPossible(vector<int>& target) {
    if (target.size() == 1)
      return target[0] == 1;

    long sum = accumulate(target.begin(), target.end(), 0L);
    priority_queue<int> maxHeap;

    for (const int num : target)
      maxHeap.push(num);

    while (maxHeap.top() > 1) {
      const long mx = maxHeap.top();
      maxHeap.pop();
      const long restSum = sum - mx;
      // Only occurs if n == 2.
      if (restSum == 1)
        return true;
      const long updated = mx % restSum;
      // updated == 0 (invalid) or didn't change.
      if (updated == 0 || updated == mx)
        return false;
      maxHeap.push(updated);
      sum = sum - mx + updated;
    }

    return true;
  }
};
/* code provided by PROGIEZ */

1354. Construct Target Array With Multiple Sums LeetCode Solution in Java

class Solution {
  public boolean isPossible(int[] target) {
    if (target.length == 1)
      return target[0] == 1;

    long sum = Arrays.stream(target).asLongStream().sum();
    Queue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

    for (final int num : target)
      maxHeap.offer(num);

    while (maxHeap.peek() > 1) {
      final long mx = maxHeap.poll();
      final long restSum = sum - mx;
      // Only occurs if n == 2.
      if (restSum == 1)
        return true;
      final long updated = mx % restSum;
      // updated == 0 (invalid) or didn't change.
      if (updated == 0 || updated == mx)
        return false;
      maxHeap.offer((int) updated);
      sum = sum - mx + updated;
    }

    return true;
  }
}
// code provided by PROGIEZ

1354. Construct Target Array With Multiple Sums LeetCode Solution in Python

class Solution:
  def isPossible(self, target: list[int]) -> bool:
    if len(target) == 1:
      return target[0] == 1

    summ = sum(target)
    maxHeap = [-num for num in target]
    heapq.heapify(maxHeap)

    while -maxHeap[0] > 1:
      mx = -heapq.heappop(maxHeap)
      restSum = summ - mx
      # Only occurs if n == 2.
      if restSum == 1:
        return True
      updated = mx % restSum
      # updated == 0 (invalid) or didn't change.
      if updated == 0 or updated == mx:
        return False
      heapq.heappush(maxHeap, -updated)
      summ = summ - mx + updated

    return True
 # code by PROGIEZ