CODEWITHSUNDEEP
algorithmdynamic-programming
Elmi Ahmadov
Elmi Ahmadov

Reputation: 1035

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

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 ?

Upvotes: 3

Views: 4931

Answers (2)

Binal Parekh
Binal Parekh

Reputation: 49

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

Upvotes: 0

Nikita Rybak
Nikita Rybak

Reputation: 68016

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.

Upvotes: 4

Related Questions