The key insight is to work backwards from the target array, always focusing on the largest element. Since each operation sets one element to the sum of the array, the largest element at any step must have been formed by adding up the previous array. By reversing the process and using a max heap, we can efficiently simulate the steps needed to reach the starting array of all ones.
The sum of all elements can exceed INT_MAX, so always use a 64-bit integer for the running sum.
If the largest element is less than or equal to the sum of the rest, it’s impossible to proceed—return false in this case.
If the sum of the rest is 1, you can always reach the starting array (all ones)—return true immediately.
If the largest element is much greater than the sum of the rest, repeated subtraction is inefficient and can cause TLE. Use the modulo operation (cur % rest) to quickly reduce the value.
import java.util.*;
classSolution {
publicbooleanisPossible(int[] target) {
PriorityQueue<Integer> pq =new PriorityQueue<>((a, b) -> b - a);
long sum = 0;
for (int x : target) {
sum += x;
pq.add(x);
}
while (pq.peek() > 1) {
int cur = pq.poll();
long rest = sum - cur;
if (rest == 1) returntrue;
if (rest == 0 || cur <= rest) returnfalse;
int prev = (int)(cur % rest);
if (prev == 0) returnfalse;
pq.add(prev);
sum = rest + prev;
}
returntrue;
}
}
import java.util.PriorityQueue
classSolution {
funisPossible(target: IntArray): Boolean {
val pq = PriorityQueue<Int>(compareByDescending { it })
var sum = 0Lfor (x in target) {
sum += x
pq.add(x)
}
while (pq.peek() > 1) {
val cur = pq.poll()
val rest = sum - cur
if (rest ==1L) returntrueif (rest ==0L|| cur <= rest) returnfalseval prev = (cur % rest).toInt()
if (prev ==0) returnfalse pq.add(prev)
sum = rest + prev
}
returntrue }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import heapq
classSolution:
defisPossible(self, target: list[int]) -> bool:
total = sum(target)
pq = [-x for x in target]
heapq.heapify(pq)
while-pq[0] >1:
cur =-heapq.heappop(pq)
rest = total - cur
if rest ==1:
returnTrueif rest ==0or cur <= rest:
returnFalse prev = cur % rest
if prev ==0:
returnFalse heapq.heappush(pq, -prev)
total = rest + prev
returnTrue
In Java, building the heap is O(n log n) since there is no direct buildHeap method; otherwise, it could be O(n).
The number of operations is effectively capped: for the worst-case input like [1, 1], it takes at most 44 steps before integer overflow, and for larger arrays (e.g., size 5 * 10^4), it takes even fewer (about 16 steps).
If the same element is updated repeatedly, the modulo operation ensures its value drops rapidly, so the process does not take excessive time.
Since all numbers are integers, the sum cannot exceed INT_MAX.
The main idea is to always focus on the largest element in the array, since it must have been formed by adding up all the other elements in a previous step. By repeatedly reducing the largest element using the sum of the rest, we can simulate the reverse process efficiently. If at any point the largest element cannot be reduced further or the process becomes invalid, we know it’s impossible to reach the starting array.
classSolution {
public:bool isPossible(vector<int>& t) {
longlong s =0;
for (int n : t) s += n;
while (true) {
int mi =0;
for (int i =1; i < t.size(); ++i) if (t[i] > t[mi]) mi = i;
longlong rest = s - t[mi];
if (t[mi] ==1|| rest ==1) return true;
if (rest ==0|| t[mi] <= rest) return false;
int prev = t[mi] % rest;
if (prev ==0) return false;
s = rest + prev;
t[mi] = prev;
}
}
};
funcisPossible(t []int) bool {
s:=0for_, n:=ranget {
s+=n }
for {
mi:=0fori:=1; i < len(t); i++ {
ift[i] > t[mi] {
mi = i }
}
rest:=s-t[mi]
ift[mi] ==1||rest==1 {
returntrue }
ifrest==0||t[mi] <=rest {
returnfalse }
prev:=t[mi] %restifprev==0 {
returnfalse }
s = rest+prevt[mi] = prev }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
publicbooleanisPossible(int[] t) {
long s = 0;
for (int n : t) s += n;
while (true) {
int mi = 0;
for (int i = 1; i < t.length; ++i) if (t[i]> t[mi]) mi = i;
long rest = s - t[mi];
if (t[mi]== 1 || rest == 1) returntrue;
if (rest == 0 || t[mi]<= rest) returnfalse;
int prev = (int)(t[mi]% rest);
if (prev == 0) returnfalse;
s = rest + prev;
t[mi]= prev;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
funisPossible(t: IntArray): Boolean {
var s = t.sum().toLong()
while (true) {
var mi = 0for (i in1 until t.size) if (t[i] > t[mi]) mi = i
val rest = s - t[mi]
if (t[mi] ==1|| rest ==1L) returntrueif (rest ==0L|| t[mi] <= rest) returnfalseval prev = (t[mi] % rest).toInt()
if (prev ==0) returnfalse s = rest + prev
t[mi] = prev
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defisPossible(self, t: list[int]) -> bool:
s = sum(t)
whileTrue:
mi = max(range(len(t)), key=lambda i: t[i])
rest = s - t[mi]
if t[mi] ==1or rest ==1:
returnTrueif rest ==0or t[mi] <= rest:
returnFalse prev = t[mi] % rest
if prev ==0:
returnFalse s = rest + prev
t[mi] = prev
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
pubfnis_possible(mut t: Vec<i32>) -> bool {
letmut s: i64= t.iter().map(|&x| x asi64).sum();
loop {
let mi = t.iter().enumerate().max_by_key(|&(_, &v)| v).unwrap().0;
let rest = s - t[mi] asi64;
if t[mi] ==1|| rest ==1 { returntrue; }
if rest ==0|| (t[mi] asi64) <= rest { returnfalse; }
let prev = (t[mi] asi64) % rest;
if prev ==0 { returnfalse; }
s = rest + prev;
t[mi] = prev asi32;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
functionisPossible(t: number[]):boolean {
lets=t.reduce((a, b) =>a+b, 0);
while (true) {
letmi=0;
for (leti=1; i<t.length; ++i) if (t[i] >t[mi]) mi=i;
letrest=s-t[mi];
if (t[mi] ===1||rest===1) returntrue;
if (rest===0||t[mi] <=rest) returnfalse;
letprev=t[mi] %rest;
if (prev===0) returnfalse;
s=rest+prev;
t[mi] =prev;
}
}
⏰ Time complexity: O(n^2), since in the worst case, for each update, we scan the array to find the maximum, and this can happen up to O(n) times for each element.
🧺 Space complexity: O(1), as we only use a constant amount of extra space beyond the input array.