3862. Find the Smallest Balanced Index
You are given an integer array nums.
An index i is balanced if the sum of elements strictly to the left of i equals the product of elements strictly to the right of i.
If there are no elements to the left, the sum is considered as 0. Similarly, if there are no elements to the right, the product is considered as 1.
Return an integer denoting the smallest balanced index. If no balanced index exists, return -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int smallestBalancedIndex(vector<int>& nums) {
long long sum = 0;
map<int,int> right;
for(int i = 1; i < nums.size(); i++) right[-nums[i]]++;
for(int i = 0; i < nums.size(); i++) {
long long prod = 1;
for(auto& [k,v] : right) {
int val = -k;
if(val == 1) continue;
for(int j = 0; j < v; j++) {
prod *= val;
if(prod > sum) break;
}
if(prod > sum) break;
}
if(prod == sum) return i;
if(sum > prod) return -1;
sum += nums[i];
if(i + 1 < nums.size())
if(--right[-nums[i+1]] == 0) right.erase(-nums[i+1]);
}
return -1;
}
};
|
