MINSTEP EDITORIAL

PROBLEM LINK:
Minimum Steps

Editorialist:Faiz Alam
Author and Tester:Prasoon Jain

PREREQUISITES

Observation,Adhoc

PROBLEM:
You are given an array of size N, consisting only of -1 and 1.Your task is to make the sum of the array equals to 0 replacing -1 by 1 or 1 by -1 only in minimum number of steps.

EXPLANATION:
Since, array consists only of 1 and -1,hence sum of array can be zero only if number of 1 equals to number of -1.For odd sized array number of 1 can never be equal to number of -1 hence sum will always be non-divisible by 2 hence return -1 (impossible),else for even sized array result would be simply be total sum of array divided by 2.

SOLUTIONS

Setter's Solution
 package codeHeat;
 import java.util.Scanner;
public class MINSTEP {
public static void main(String[] args) {
	
	Scanner sc=new Scanner(System.in);
	int t=sc.nextInt();
	while(t>0) {
		int n=sc.nextInt();
		int arr[]=new int[n];
		int sum=0;
		for(int i=0;i<n;i++) {
			arr[i]=sc.nextInt();
			sum=sum+arr[i];
		}
		if(sum%2!=0)
			System.out.println("-1");
		else 
			System.out.println(sum/2);
		t--;
	}
}
}

complexity-O(N)

1 Like