 Author: Utkarsh Gupta
Tester: Tejas Pandey
Editorialist: Daanish Mahajan

Easy Medium

# PREREQUISITES:

Prefix sums, \mathcal{O}(N^{1/2}) factorization

# PROBLEM:

You are given an array A of length N.
You can perform the following operation on the array, as long as it has more than one element:

• Choose any two adjacent elements, remove them from the array and insert their sum at that position.

Print the minimum number of operations to be applied on array A such that all the elements in the resulting array are equal.

# EXPLANATION:

Hint 1

Only consecutive elements are getting merged which means elements of the final array can be visualized as the sum of elements of some subarray of the original array A.

Hint 2
• The length of the final array is some factor of the sum of the array.
• The value of the final array is some factor of the sum of the array.
Solution

Suppose B is the final array where each element of B = x and size of B = y.

This means the original array A can be partitioned into subarrays [1 \ldots P_1], [P_1 + 1, \ldots P_2], \ldots, [P_{y - 2} + 1, \ldots, P_{y - 1}], [P_{y - 1} + 1, N] (P_i < P_{i + 1}, \forall i \in [1, y - 2] and P_1 \ge 1 and P_{y - 1} \lt N) where each of these subarray sums to x.

Suppose sum of elements of A = S and the prefix sum array of A is C.

Also, the sum of elements of B is equal to the sum of elements of A, implying:
x \cdot y = S.

This means x is a factor of S. So now for all factors of S, we check whether a particular factor is valid, i.e, there exists a sequence of moves such that the final array B has all elements equal to that factor and take minimum over the count of operations required over all valid factors.

Implementation

Initialize answer to N - 1 since one of the valid options is to merge all the elements into a single element.
Now we iterate over the factors (x) of S and check whether there exists indices i_1 \lt i_2, \ldots \lt i_{y - 2} \lt i_{y - 1} in C (where y = \frac{S}{x}) such that C_{i_c} = c \cdot x, \forall c \in [1, y - 1], and if it does, update answer = min(answer, N - y). This takes \mathcal{O}(N) time for each factor.

Corner case

For S = 0, answer = N - (count of indices have value equal to $0$ in $P$).

# COMPLEXITY ANALYSIS:

Complexity = \mathcal{O}(count of factors of S \cdot checking whether a factor is valid).
Since maximum value of S = N \cdot maximum value of A_i = \mathcal{O}(N^2) and maximum number of factors of a number X = \mathcal{O}(X^{1/3}) and we are we can validate every factor in \mathcal{O}(N), the above expression turns out to be \mathcal{O}(N^{5/3}).

# SOLUTIONS:

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
void solve()
{
ll n;
cin>>n;
ll arr[n+1]={0};
ll sum=0;
for(int i=1;i<=n;i++)
{
cin>>arr[i];
sum+=arr[i];
}
if(sum==0)
{
ll tmp=0;
ll ans=n;
for(int i=1;i<=n;i++)
{
tmp+=arr[i];
if(tmp==0)
ans--;
}
cout<<ans<<'\n';
return;
}
if(sum<0)
{
for(int i=1;i<=n;i++)
arr[i]*=-1;
sum*=-1;
}
ll out=n-1;
for(int i=1;i*i<=sum;i++)
{
if((sum%i)!=0)
continue;
{
int x=i;
ll tmp=0;
ll ans=n;
int flag=1;
int cnt=0;
for(int j=1;j<=n;j++)
{
tmp+=arr[j];
if(tmp==x)
{
ans--;
cnt++;
tmp=0;
}
}
if(cnt*x>=sum)
out=min(out,n-sum/x);
}
{
int x=sum/i;
ll tmp=0;
ll ans=n;
int flag=1;
int cnt=0;
for(int j=1;j<=n;j++)
{
tmp+=arr[j];
if(tmp==x)
{
ans--;
cnt++;
tmp=0;
}
}
if(cnt*x>=sum)
out=min(out,n-sum/x);
}
}
cout<<out<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin>>t;
while(t--)
solve();
}

Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main() {
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; i++) cin >> a[i];
ll sm = 0;
ll pa[n];
pa = a;
for(int i = 1; i < n; i++) pa[i] = pa[i - 1] + a[i];
sm = pa[n - 1];
if(!sm) {
int blocks = 0;
for(int i = 0; i < n; i++)
blocks += (!pa[i]);
cout << n - blocks << "\n";
continue;
}
int ans = n - 1;
int absm = abs(sm);
for(int i = 1; i <= sqrt(absm); i++) {
if(absm%i == 0) {
ll tf = sm/i;
ll now = tf;
int ok = 0;
for(int j = 0; j < n; j++) {
if(pa[j] == now) {
if(now == sm) ok = 1;
now += tf;
}
}
if(ok) ans = min(ans, n - i);
if(absm/i != i) {
ll tf = sm/(absm/i);
ll now = tf;
int ok = 0;
for(int j = 0; j < n; j++) {
if(pa[j] == now) {
if(now == sm) ok = 1;
now += tf;
}
}
if(ok) ans = min(ans, (int)(n - absm/i));
}
}
}
cout << ans << "\n";
}
return 0;
}

Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int maxn = 3e4 + 10;
int n;
int a[maxn], ps[maxn];
int cal(int x){
int mul = 1;
for(int i = 1; i <= n && mul < ps[n] / x; i++){
if(ps[i] == mul * x){
mul++;
}
}
if(mul != ps[n] / x)mul = 1;
return n - mul;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int t; cin >> t;
while(t--){
cin >> n;
int cnt0 = 0;
for(int i = 1; i <= n; i++){
cin >> a[i];
ps[i] = ps[i - 1] + a[i];
cnt0 += ps[i] == 0;
}
int ans = ps[n] ? n - 1 : n - cnt0;
for(int i = 1; i * i <= abs(ps[n]); i++){
if(ps[n] % i)continue;
ans = min(ans, min(cal(i * (ps[n] / abs(ps[n]))), cal(ps[n] / i)));
}
cout << ans << endl;
}
return 0;
}

2 Likes

Can you please explain why my solution is showing SIGFPE Run time error only for 1st subtask and giving right answer for all other 12 tasks.
Solution : solution

1 Like

Consider Case-

1
7
1 1 1 3 -2 2 -4


Correct ans- 5

7 Likes

Can you please explain why my solution is showing WA for 1st subtask only?

My code: Solution: 57783955 | CodeChef

2 Likes
3 Likes

My code is giving output 5 is it correct as my code is also showing wrong answer on 1st test case only

1 Like

giving WA in 1st testCase ,please give any TestCase for which i’m getting WA.
https://www.codechef.com/viewsolution/57947972

1 Like

2 0 8 -4 -2 2 2 2 0
try for this one
your code is working fine for whatever testcases i tried for my code

1 Like

Here’s the link for my code:
https://www.codechef.com/viewsolution/57900183

Your code doesn’t print anything on that input.

1 Like

getting 8 , is it correct?

sir can u explain how 5 is the correct answer for this case…?

I am getting WA only for test case #1. Here is the link for code: Solution: 57951338 | CodeChef. Can someone provide the case for which it is failing.

1 2 3 -2 2 -4
1 5 -2 2 -4
1 3 2 -4
1 5 -4
1 1

2 Likes

Not able to find any testcase where my code is failing
Can anyone please point out the testcase where it is giving unexpected output

https://www.codechef.com/viewsolution/57879755

similar but smaller corner case
1
4
1 1 1 -1
correct ans: 2

2 Likes

On codechef ide it isn’t printing anything I was using Leetcode playground there it printed 5. Thanks for pointing it out. Let me check what’s the error.

Thank you @jagdish_t19 for the testcase
1
4
1 1 1 -1

1 Like