Page Contents
Remove Adjacent Solution Codechef
You are given an array AA of length NN.
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||A|, you can choose an index 1≤i<|A|1≤i<|A|, and transform the array into [A1,A2,…,Ai−1,Ai+Ai+1,Ai+2,…,AN][A1,A2,…,Ai−1,Ai+Ai+1,Ai+2,…,AN].
Note that after each operation, the length of array decreases by exactly 11.
Print the minimum number of operations to be applied on array AA 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 TT, denoting the number of test cases. The description of TT test cases follows.
- Each test case consists of two lines of input.
- The first line contains an integer NN.
- The second line contains NN space-separated integers, the elements of array AA.
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≤1041≤T≤104
- 2≤N≤3⋅1042≤N≤3⋅104
- −3⋅104≤Ai≤3⋅104−3⋅104≤Ai≤3⋅104
- Sum of NN over all test cases does not exceed 3⋅1043⋅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 11: It is optimal to remove A2A2 and A3A3 in the first operation, after which the array becomes [5,5][5,5] — all of whose elements are equal.
Test case 22: Remove A1A1 and A2A2 after which the array becomes [15][15], which contains equal elements because it is of length 11.
Test case 33: First remove A3A3 and A4A4 after which the updated array AA becomes [3,6,9,9][3,6,9,9]. Now remove A1A1 and A2A2 after which the array becomes [9,9,9][9,9,9].
Test case 44: 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);; } } }
February Long Challenge 2022 Solution
- Random OR Solution Codechef
- Digit Multiplication By K Solution Codechef
- Remove Adjacent Solution Codechef
- Bitwise Blend Solution Codechef
- Binary Base Basics Solution Codechef
- N Queens Puzzle Solved ! Solution Codechef
- Chef and the Hair Salon Solution Codechef
January Long Challenge 2022 Solution
- TCS Examination EXAMTIME Solution Codechef
- Chef and Fixed Deposits MINFD Solution Codechef
- Crying Colours CRYCOLR Solution Codechef
- Power Sum POWSUM Solution Codechef
- Sum and OR SUMANDOR Solution Codechef
- Tree Master TRMT Solution Codechef
- Array Partition ARRPART Solution Codechef
- Keplers Law KEPLERSLAW Solution
- Covid Spread COVSPRD Solution
- Prime in a binary string PINBS Solution
- Retrieve back the Array XORED Solution
- Chef and Riffles RIFFLES Solution
- Sequence Master MASTER Solution
- Generating Cycles GENECYC Solution
#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;
}