Lucky Tickets (count an amount of lucky numbers, having the specified sum of ALL digits)

Question

Here is the problem

You are given a number 1 ≤ N ≤ 50. Every ticket has its 2N-digit number. We call a ticket lucky, if the sum of its first N digits is equal to the sum of its last N digits. You are also given the sum of ALL digits in the number. Your task is to count an amount of lucky numbers, having the specified sum of ALL digits.

For input 2 2 output is 4 (0101, 0110, 1001, 1010)

Can you help me to solve this problem? What is the minimum complexity ?

Answer 1

If required sum is s, then each half must have sum s/2. Now, you need to find f(n, s/2): how many n-digit numbers have sum of digits s/2. Knowing f(n, s/2), you can get the answer in one line (try figuring it out yourself).

As for how to calculate f(n, m): that's the standard DP. You have recursive formula like f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9). Here, 0, 1, 2, .. 9 are all possible options for the last digit of the given number. If last digit is k, then the rest is (n-1)-long number with sum of digits m - k.

Hope it helps.

PS According to the problem constraints, you'll need some kind of long arithmetics to pass it.

Answer 2

private static boolean isLucky(int n) {

    int sum1 = 0;
    int sum2 =0;
    String s = String.valueOf(n);
    System.out.println("After Conversion in String= " + s);
    for (int i = 0; i < (s.length()) / 2; i++) {
        System.out.println("half string === " + s.charAt(i));
        sum1 = sum1 + Character.getNumericValue(s.charAt(i));
    }
    System.out.println("half sum === " + sum1);
    for(int j=(s.length()) / 2 ; j< s.length();j++){
        System.out.println("half string === " + s.charAt(j));
        sum2 = sum2 + Character.getNumericValue(s.charAt(j));
    }
    System.out.println("another half sum === " + sum2);
    if(sum1 == sum2){
        return true;
    }
    return false;
}