BINXOR solution failed for larger n values ( Java)

general
1

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;
    }
}
2

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

1 Like
3

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

4

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)).

5

I am getting WA not TLE.

6

Yes you did :slight_smile:

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
7

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

1 Like