# BINXOR solution failed for larger n values ( Java)

I got only 10 points for the below code . I have watched the editorial and it’s using the same approach as mine. Any suggestions welcome as to why this happened.

``````import java.util.Scanner;

class Codechef {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
try{
String u = sc.nextLine();
int t = Integer.parseInt(u);
while (t-- > 0) {
int n = Integer.parseInt(sc.nextLine());
String a = sc.nextLine();
String b = sc.nextLine();
int z1 = 0, o1 = 0, z2 = 0, o2 = 0;
for (int i = 0; i < n; i++) {
if (a.charAt(i) == '0') {
z1 += 1;
} else {
o1 += 1;
}
}
for (int i = 0; i < n; i++) {
if (b.charAt(i) == '0') {
z2 += 1;
} else {
o2 += 1;
}
}
int m = Math.abs(o1 - o2);
int d = Math.min(z1, o2) + Math.min(z2, o1);
int sum = 0;
if (d < m) {
System.out.println("0");
continue;
}
for (int i = m; i <= d; i += 2) {
sum = modulus(sum, n, i);
}
System.out.println(sum);
}
}
catch(Exception e){}
}
public static int modulus(int sum,int n,int k){
int num=comb(n,k);
sum=( (sum%1000000007) +(num%1000000007) )%1000000007;
return sum;
}
public static int comb(int n,int k){
if(k==1)
return n;
if(k==n)
return 1;
int denom=1;
int num=1;
for (int i = 2; i <=n; i++) {
num=( (num%1000000007) * (i%1000000007) )%1000000007;
}
for (int i = 2; i <=k; i++) {
denom=( (denom%1000000007) * (i%1000000007) )%1000000007;
}
for (int i = 2; i <=n-k; i++) {
denom=( (denom%1000000007) * (i%1000000007) )%1000000007;
}
num=( num / denom )%1000000007;
return num;
}
}``````

Are u using this - (a/b)%m=(a%m)/(b%m)?
This is incorrect way of using modulus on division

1 Like

Nope. I know it holds for only +,- ,*.
For / I didn’t use that.

you are calculating comb in O(n), this will give TLE.
See this code, approach is same but i am calculating comb(ncr in my code) in O(log(n)).

I am getting WA not TLE.

Yes you did

This is why `comb(20, 2)` gives the answer `0` when it should be `190`.

Edit:

Also, you’re almost certainly going to overflow an `int` calculating n! for large-ish n.

Edit2:

``````int factorialInt = 1;
long factorialLong = 1;
for (int i = 1; i <= 100000; i++)
{
factorialInt = (factorialInt * i) % 1000000007;
factorialLong = (factorialLong * i) % 1000000007;
System.out.println("i: " + i  + " factorialInt: " + factorialInt + " factorialLong: " + factorialLong);
if (factorialInt != factorialLong)
{
System.out.println("Whoops lol");
}
}
``````

gives:

``````i: 1 factorialInt: 1 factorialLong: 1
i: 2 factorialInt: 2 factorialLong: 2
i: 3 factorialInt: 6 factorialLong: 6
i: 4 factorialInt: 24 factorialLong: 24
i: 5 factorialInt: 120 factorialLong: 120
i: 6 factorialInt: 720 factorialLong: 720
i: 7 factorialInt: 5040 factorialLong: 5040
i: 8 factorialInt: 40320 factorialLong: 40320
i: 9 factorialInt: 362880 factorialLong: 362880
i: 10 factorialInt: 3628800 factorialLong: 3628800
i: 11 factorialInt: 39916800 factorialLong: 39916800
i: 12 factorialInt: 479001600 factorialLong: 479001600
i: 13 factorialInt: 932053497 factorialLong: 227020758
Whoops lol
i: 14 factorialInt: 163847070 factorialLong: 178290591
Whoops lol
i: 15 factorialInt: -837261239 factorialLong: 674358851
``````

etc.

2 Likes

I will work on that and update the same here. Thanks

1 Like