Remove Adjacent Solution Codechef

by

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

January Long Challenge 2022 Solution

1 thought on “Remove Adjacent Solution Codechef”

  1. #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;
    }

    Reply

Leave a Comment

17 − 14 =