Lucky Tickets (подсчитайте количество счастливых номеров, указав сумму ВСЕХ цифр)

Question

Вот проблема

Вам предоставляется номер 1 ≤ N ≤ 50. Каждый билет имеет свой 2N-значный номер. Мы называем билет счастливым, если сумма его первых N цифр равна сумме его последних N цифр. Вам также дается сумма ВСЕХ цифр в номере. Ваша задача - подсчитать количество счастливых чисел, указав сумму ВСЕХ цифр.

Для входа 2 2 выход равен 4 (0101, 0110, 1001, 1010)

Можете ли вы помочь мне решить эту проблему? Какова минимальная сложность?

Answer 1

Если требуемая сумма s, то каждая половина должна иметь сумму s/2.Теперь вам нужно найти f(n, s/2): сколько n-значных чисел имеет сумму цифр s/2.Зная f(n, s/2), вы можете получить ответ в одну строку (попробуйте выяснить это самостоятельно).

Что касается того, как рассчитать f(n, m): это стандартное DP.У вас есть рекурсивная формула типа f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9).Здесь 0, 1, 2, .. 9 - это все возможные варианты последней цифры данного номера.Если последняя цифра - k, то остальное - (n-1) -длинное число с суммой цифр m - k.

Надеюсь, это поможет.

PS В соответствии с ограничениями задачи выпонадобится какая-то длинная арифметика, чтобы пройти его.

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