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)