Glück Tickets (eine Menge an Glückszahlen zählen, die angegebene Summe aller Ziffern mit)

Question

Hier ist das Problem

  

Sie sind eine Zahl 1 ≤ N ≤ 50. Jedes gegebene Ticket hat seine 2N-stellige Nummer. Wir nennen ein Ticket Glück, wenn die Summe seiner ersten N Ziffern gleich der Summe seiner letzten N Ziffern ist. Sie sind auch die Summe aller Ziffern der Nummer. Ihre Aufgabe ist es, eine Menge von Glückszahlen zu rechnen, die angegebene Summe aller Ziffern hat.

Eingang 2 2 4 ausgegeben wird (0101, 0110, 1001, 1010)

Können Sie mir helfen, dieses Problem zu lösen? Was ist die minimale Komplexität?

Answer 1

Bei Bedarf Summe s ist, dann muss jede halbe Summe s/2 haben. Nun müssen Sie f(n, s/2) finden: Wie viele n-stellige Zahlen Summe von Ziffern s/2 haben. Zu wissen, f(n, s/2), können Sie die Antwort in einer Zeile erhalten (versuchen Sie es selbst herauszufinden).

Was, wie f(n, m) berechnen: die den Standard DP ist. Sie haben Rekursionsformel wie f(n, m) = f(n-1, m) + f(n-1, m-1) + f(n-1, m-2) + ... + f(n-1, m-9). Hier 0, 1, 2, .. 9 sind alle möglichen Optionen für die letzte Ziffer der angegebenen Zahl. Wenn letzte Ziffer k ist, dann der Rest ist (n-1) lange Zahl mit Ziffernsumme m - k.

Hope es hilft.

PS Nach dem Problem Zwängen, werden Sie eine Art langer arithmetics müssen es passieren.

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