Remove Adjacent Solution Codechef

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≤10⁴
• 2≤N≤3⋅10⁴
• −3⋅10⁴≤Ai≤3⋅10⁴
• Sum of N over all test cases does not exceed 3⋅10⁴

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);;
		}
	}
}

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