Can anybody please tell me why i am getting wrong answer:-
Link to my solution: CodeChef: Practical coding for everyone
But, if you are considering the complexity for input. then, there can’t be any algorithm better than O(n).
1 Like
@ajinkyagore can you please tell me what’s wrong this code.
import java.util.;
import java.math.;
class Coke{
public static void main(String args[]){
Scanner s=new Scanner(System.in);
int t=s.nextInt();
int n=0;
for(int k=0;k<t;k++){
if(k>0) System.out.println();
n=s.nextInt();
String[] arr=new String[n];
String str=s.nextLine();
for(int j=0;j<n;j++){
arr[j]=s.nextLine();
}
int sum=0;
int[] diff=new int[n];
for(int i=0;i<n;i++){
int count=0;
for(int j=0;j<n/2;j++){
if(arr[i].charAt(j)==‘1’) count++;
}
for(int j=n/2;j<n;j++){
if(arr[i].charAt(j)==‘1’) count–;
}
diff[i]=count;
sum+=count;
}
//Arrays.sort(diff);
int min=sum;
for(int j=0;j<n;j++){
//System.out.println(arr[j]);
int val=sum-2*diff[j];
if(Math.abs(val)<min) min=Math.abs(val);
}
System.out.print(min);
}
}
}
@taran_1407, can you please tell me why is this code giving time limit exceeded
import java.util.;
import java.math.;
class Coke{
public static void main(String args[]){
Scanner s=new Scanner(System.in);
int t=s.nextInt();
int n=0;
for(int k=0;k<t;k++){
if(k>0) System.out.println();
n=s.nextInt();
String[] arr=new String[n];
String str=s.nextLine();
for(int j=0;j<n;j++){
arr[j]=s.nextLine();
}
int sum=0;
int[] diff=new int[n];
for(int i=0;i<n;i++){
int count=0;
for(int j=0;j<n/2;j++){
if(arr[i].charAt(j)==‘1’) count++;
}
for(int j=n/2;j<n;j++){
if(arr[i].charAt(j)==‘1’) count–;
}
diff[i]=count;
sum+=count;
}
//Arrays.sort(diff);
int min=sum;
for(int j=0;j<n;j++){
//System.out.println(arr[j]);
int val=sum-2*diff[j];
if(Math.abs(val)<min) min=Math.abs(val);
}
System.out.print(min);
}
}
}
O(t * (n n + n ) ) which is approximately O(t(n^2)
Got it now… Thanks
Remove whole code and post link to sol.
hey what is the complexity of your solution bro??
because if it is n^2 than your code is way too much of lines.
It’s not N^2 … I think its O(nlogn) because of sorting
(I’m very poor at finding time complexity of any algorithm)
hey plz help i dont get where my code lags!!
#include<bits/stdc++.h>
using namespace std;
int main(){
//freopen(“input.txt”,“r”,stdin);
//freopen(“output.txt”,“w”,stdout);
ios::sync_with_stdio(0);
cin.tie(0);
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
char matrix[n][n];
// input matrix and calculate total sum
int tsum=0,lsum=0;
int minn=1000000000;
for(int i=0;i<n;i++){
int lrowsum=0,rrowsum=0;
for(int j=0;j<n;j++){
scanf("%c",&matrix[i][j]);
int r=(int)matrix[i][j];
tsum=tsum+r;
if(j<n/2){
lsum=lsum+r;
lrowsum=lrowsum+r;
}
else{
rrowsum=rrowsum+r;
}
minn=min(abs(2*lsum-tsum-2*abs(lrowsum+rrowsum)),minn);
}
}
printf("%d\n",minn );
}
return 0;
}
it is giving wrong output !! but my logic maches as given in editorial! plz help i am trying from long time.
In all the loops change prefix operators to postfix operators.
If you don’t know what they are read this.
It is true that your logic is the same as given in the editorial but you are messing up with ascii values.
The ascii value of 0 is 48 and 1 is 49
Thus, r will either be 48 or 49 and not 0 or 1.
That’s your bug which I caught on first glance through he code.
I dont think there should be more 
but i typecast my value to int
That is the reason…
The character ‘0’ has an decimal value of 48 in the integer list.
If you want more explanation, see ASCII - Simple English Wikipedia, the free encyclopedia
Here, the character ‘0’ has decimal value 48 and character ‘1’ has decimal value 49
Problem:
int sum = 0;
for(int i=0;i<n;i++)
sum+=a[i];
int ans = abs(sum);
for(int i=0;i<n;i++)
{
ans = min(ans , abs(sum - 2*a[i]));
}
Anybody explain me above part of Setter1 Solution.
for 1st Testcase: a[]=1,1,1,1,0,0
for 2nd Testcase: a[]=-2,2,1,-1
what happened after that?
Please, explain logic behind that 
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner k = new Scanner(System.in);
int n=k.nextInt();
while(n>0){
int totalstr=k.nextInt();
int arr[][]=new int[totalstr][totalstr];
int leftsum=0,rightsum=0;
k.nextLine();
for(int j=0;j<totalstr;j++){
String str=k.nextLine();
for(int i=0;i<str.length();i++){
if(i<str.length()/2){
if(str.charAt(i)=='1'){
leftsum++;
arr[j][i]=1;
}
}else{
if(str.charAt(i)=='1'){
rightsum++;
arr[j][i]=1;
}
}
}
}
if(Math.abs(leftsum-rightsum)==0){
System.out.println(0);
return;
}
int min=1000;
for(int a=0;a<arr.length;a++){
int x=0,y=0;
for(int b=0;b<arr.length;b++){
if(arr[a][b]==1&&b<arr.length/2){
x++;
}else if(arr[a][b]==1&&b>=arr.length/2){
y++;
}
}
int ans=Math.abs(leftsum-x+y-(rightsum-y+x));
if(min>ans){
min=ans;
}
}
System.out.print(min);
n--;}
}}what s the error is in my code