Remove Adjacent Solution Codechef
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.
- Formally, if the current length of the array is |A|, you can choose an index 1≤i<|A|, and transform the array into [A1,A2,…,Ai−1,Ai+Ai+1,Ai+2,…,AN].
Note that after each operation, the length of array decreases by exactly 1.
Print the minimum number of operations to be applied on array A such that all the elements in the resulting array are equal. See sample explanation for more details.
Input Format
- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- Each test case consists of two lines of input.
- The first line contains an integer N.
- The second line contains N space-separated integers, the elements of array A.
Output Format
For each test case, output on a new line the minimum number of operations required to make all the elements equal.
Constraints
- 1≤T≤104
- 2≤N≤3⋅104
- −3⋅104≤Ai≤3⋅104
- Sum of N over all test cases does not exceed 3⋅104
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4
3
5 2 3
2
6 9
5
3 6 5 4 9
3
3 3 3
Sample Output 1
1
1
2
0
Explanation
- Test case 1: It is optimal to remove A2 and A3 in the first operation, after which the array becomes [5,5] all of whose elements are equal.
- Test case 2: Remove A1 and A2 after which the array becomes [15], which contains equal elements because it is of length 1.
- Test case 3: First remove A3 and A4 after which the updated array A becomes [3,6,9,9]. Now remove A1 and A2 after which the array becomes [9,9,9].
- Test case 4: The array elements are already equal.
SOLUTION
Program: Remove Adjacent Solution in Python
def partitions2(array, n, K):
if (e%K != 0):
return False
temp = 0
count = n - K
c = False
imp = True
cursum = 0
for i in range(n):
if (count<0):
imp = False
break
if (cursum + array[i] == e/K) and (temp<=K):
temp += 1
c = False
cursum = 0
elif (cursum + array[i] == -e/K) and (temp>K):
temp = temp - 1
c = False
cursum = 0
else:
cursum += array[i]
if c:
count = count - 1
c = True
if (count<0):
imp = False
return ((temp==K) and imp)
x = int(input())
for i in range(x):
N = int(input())
l = list(map(int,input().split()))
e = sum(l)
for i in range(N,0,-1):
k = i
if (partitions2(l, N, k)):
val = k
break
print(N-val)
Program: Remove Adjacent Solution in C++
#include <bits/stdc++.h>
#include<vector>
#include<string>
using namespace std;
int main() {
int test;
cin>>test;
while(test--)
{
int n;
cin>>n;
vector<int> v(n);
int sum = 0;
vector<int> psum(n);
for(int i=0; i<n; i++)
{
cin>>v[i];
sum=sum+v[i];
psum[i]=sum;
}
int ans;
for(int k=n; k>=1; k--)
{
if(sum%k) continue;
int counter = 1;
for(int i=0; i<n; i++)
{
if(psum[i] == (counter*(sum/k))) counter++;
}
if(counter-1 <k) continue;
ans = n-k;
break;
}
cout<<ans<<endl;
}
return 0;
}
Program: Remove Adjacent Solution in Java
import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0){
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = sc.nextInt();
}
int res = -1;
int[] prefix = new int[n];
prefix[0] = arr[0];
for(int i = 1;i<n;i++){
prefix[i] = prefix[i-1]+arr[i];
}
HashMap<Integer,Integer> map = new HashMap<>();
for(int curr : prefix){
if(map.containsKey(curr) && map.get(curr)>0) continue;
map.put(curr,map.getOrDefault(curr,0)+1);
int sum = 0;
int total = 0;
int count = 0;
for(int i=0;i<n;i++){
sum += arr[i];
total+=arr[i];
if(sum==curr){
count++;
sum = 0;
if(prefix[n-1]==total) res = Math.max(res,count);
}
}
if(sum!=0) count=0;
res = Math.max(res,count);
}
System.out.println(n-res);;
}
}
}
#include
using namespace std;
int main() {
int t;
cin >> t;
while(t–){
int n,count =0,ans =0;
cin >> n;
int arr[n];
for(int i=0;i> arr[i];
}
if(n==2){
cout << "1" << endl;
} else {
for(int i=0;i<n;i++){
if(arr[i] != arr[i+1]){
ans =1;
}
}
if(ans =0){
cout << "0" << endl;
} else{
int largest = arr[0];
for(int i=0;i largest){
largest = arr[i];
}
}
for(int i=0;i<n;i++){
if(largest == arr[i]){
// i++;
} else{
i++;
count++;
}
}
cout << count << endl;
count = 0;
}
}
}
return 0;
}