Construct target array with multiple sums

Array Heap (Priority Queue)

36.8% acceptance

Feb 25, 2026

2114

176

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn is_possible(target: Vec<i32>) -> bool {
    use std::collections::BinaryHeap;
    let mut heap: BinaryHeap<i64> = target.iter().map(|&x| x as i64).collect();
    let total: i64 = target.iter().map(|&x| x as i64).sum();
    let mut sum = total;
    loop {
      let max = heap.pop().unwrap();
      if max == 1 { return true; }
      let rest = sum - max;
      if rest <= 0 { return false; }
      // max = prev + rest  => prev = max % rest (with special case)
      let prev = if rest == 1 { 1 } else { max % rest };
      if prev == 0 || prev == max { return false; }
      sum = sum - max + prev;
      heap.push(prev);
    }
  }
}