Nehmen wir an, wir haben eine nicht negative Ganzzahl, die "heftig" (dh "schwer") ist, wenn ihr durchschnittlicher Ziffernwert größer als 7 ist.

Die Nummer 6959 ist "heftig", weil:

(6 + 9 + 5 + 9) / 4 = 7,5

Die Nummer 1234 ist nicht, weil:

(1 + 2 + 3 + 4) / 4 = 2,5

Schreiben Sie eine Funktion in einer beliebigen Sprache,

HeftyDecimalCount(a, b)

Wenn zwei positive ganze Zahlen a und b angegeben werden, wird eine ganze Zahl zurückgegeben, die angibt, wie viele "kräftige" ganze Zahlen sich innerhalb des Intervalls [a..b] einschließlich befinden.

Zum Beispiel mit a = 9480 und b = 9489:

9480   (9+4+8+0)/4 21/4 = 5.25 
9481   (9+4+8+1)/4 22/4 = 5.5
9482   (9+4+8+2)/4 23/4 = 5.75  
9483   (9+4+8+3)/4 24/4 = 6    
9484   (9+4+8+4)/4 25/4 = 6.25     
9485   (9+4+8+5)/4 26/4 = 6.5 
9486   (9+4+8+6)/4 27/4 = 6.75  
9487   (9+4+8+7)/4 28/4 = 7
9488   (9+4+8+8)/4 29/4 = 7.25   hefty 
9489   (9+4+8+9)/4 30/4 = 7.5    hefty

Zwei der Zahlen in diesem Bereich sind "heftig" und daher sollte die Funktion 2 zurückgeben.

Einige Richtlinien:

• Nehmen Sie an, dass weder a noch b 200.000.000 überschreiten.
• Eine n-Quadrat-Lösung wird funktionieren, aber langsam sein - wie schnell können wir das lösen?

Das Problem kann in O (Polylog (b)) gelöst werden.

Wir definieren f(d, n)die Anzahl der Ganzzahlen mit bis zu d Dezimalstellen, wobei die Ziffernsumme kleiner oder gleich n ist. Es ist ersichtlich, dass diese Funktion durch die Formel gegeben ist

Lassen Sie uns diese Funktion ableiten und mit etwas Einfacherem beginnen.

Die Funktion h zählt die Anzahl der Möglichkeiten, d - 1 Elemente aus einer Mehrfachmenge mit n + 1 verschiedenen Elementen auszuwählen. Dies ist auch die Anzahl der Möglichkeiten, n in d-Bins zu unterteilen. Dies lässt sich leicht erkennen, wenn man d-1-Zäune um n baut und jeden getrennten Abschnitt aufsummiert. Beispiel für n = 2, d = 3 ':

3-choose-2     fences        number
-----------------------------------
11             ||11          002
12             |1|1          011
13             |11|          020
22             1||1          101
23             1|1|          110
33             11||          200

Also zählt h alle Zahlen mit einer Ziffernsumme von n und d Ziffern. Außer es funktioniert nur für n weniger als 10, da die Ziffern auf 0 - 9 begrenzt sind. Um dies für die Werte 10 - 19 zu korrigieren, müssen wir die Anzahl der Partitionen mit einem Fach mit einer Nummer größer als 9 subtrahieren, die ich ab jetzt als übergelaufene Fächer bezeichnen werde.

Dieser Term kann berechnet werden, indem h wie folgt wiederverwendet wird. Wir zählen die Anzahl der Möglichkeiten, um n - 10 zu partitionieren, und wählen dann einen der Behälter aus, in den die 10 eingefügt werden soll, was dazu führt, dass die Anzahl der Partitionen einen übergelaufenen Behälter aufweist. Das Ergebnis ist die folgende vorläufige Funktion.

Wir fahren auf diese Weise für n kleiner oder gleich 29 fort, indem wir alle Arten der Partitionierung von n - 20 zählen und dann 2 Fächer auswählen, in die wir die Zehner einfügen, wodurch wir die Anzahl der Fächer mit 2 überfüllten Fächern zählen.

Aber an diesem Punkt müssen wir vorsichtig sein, da wir bereits die Partitionen gezählt haben, die in der vorherigen Amtszeit 2 übergelaufene Fächer hatten. Außerdem haben wir sie zweimal gezählt. Lassen Sie uns ein Beispiel verwenden und die Partition (10,0,11) mit der Summe 21 betrachten. Im vorherigen Term haben wir 10 subtrahiert, alle Partitionen der verbleibenden 11 berechnet und die 10 in eine der 3 Klassen gelegt. Diese Partition kann jedoch auf zwei Arten erreicht werden:

(10, 0, 1) => (10, 0, 11)
(0, 0, 11) => (10, 0, 11)

Da wir diese Partitionen auch einmal im ersten Term gezählt haben, beträgt die Gesamtanzahl der Partitionen mit 2 übergelaufenen Bins 1 - 2 = -1, sodass wir sie durch Hinzufügen des nächsten Terms erneut zählen müssen.

Wenn wir etwas genauer darüber nachdenken, stellen wir bald fest, dass die Häufigkeit, mit der eine Partition mit einer bestimmten Anzahl überlaufener Bins in einem bestimmten Begriff gezählt wird, durch die folgende Tabelle ausgedrückt werden kann (Spalte i steht für Begriff i, Zeile j, Partitionen mit j überlaufenen Bins) Behälter).

1 0 0 0 0 0 . .
1 1 0 0 0 0 . .
1 2 1 0 0 0 . .
1 4 6 4 1 0 . .
. . . . . . 
. . . . . . 

Ja, es ist Pascals Dreieck. Die einzige Anzahl, die uns interessiert, ist die in der ersten Zeile / Spalte, dh die Anzahl der Partitionen mit Null übergelaufenen Fächern. Und da die alternierende Summe jeder Zeile außer der ersten gleich 0 ist (z. B. 1 - 4 + 6 - 4 + 1 = 0), werden wir sie auf diese Weise los und gelangen zur vorletzten Formel.

Diese Funktion zählt alle Zahlen mit d Ziffern, die eine Ziffernsumme von n haben.

Was ist nun mit den Zahlen, deren Ziffernsumme kleiner als n ist? Wir können eine Standardwiederholung für Binomialzahlen plus ein induktives Argument verwenden, um dies zu zeigen

zählt die Anzahl der Partitionen mit höchstens n Ziffernsummen. Und daraus kann f mit den gleichen Argumenten wie für g abgeleitet werden.

Mit dieser Formel können wir zum Beispiel die Anzahl der schweren Zahlen im Intervall von 8000 bis 8999 ermitteln 1000 - f(3, 20), da sich in diesem Intervall tausend Zahlen befinden und wir die Anzahl der Zahlen mit einer Ziffernsumme von 28 oder weniger subtrahieren müssen Dabei wird berücksichtigt, dass die erste Ziffer bereits 8 zur Ziffernsumme beiträgt.

Als komplexeres Beispiel betrachten wir die Anzahl der schweren Zahlen im Intervall 1234..5678. Wir können zuerst in Schritten von 1 von 1234 bis 1240 gehen. Dann gehen wir in Schritten von 10 von 1240 bis 1300. Die obige Formel gibt uns die Anzahl der schweren Zahlen in jedem solchen Intervall:

1240..1249:  10 - f(1, 28 - (1+2+4))
1250..1259:  10 - f(1, 28 - (1+2+5))
1260..1269:  10 - f(1, 28 - (1+2+6))
1270..1279:  10 - f(1, 28 - (1+2+7))
1280..1289:  10 - f(1, 28 - (1+2+8))
1290..1299:  10 - f(1, 28 - (1+2+9))

Jetzt gehen wir von 1300 bis 2000 in Schritten von 100:

1300..1399:  100 - f(2, 28 - (1+3))
1400..1499:  100 - f(2, 28 - (1+4))
1500..1599:  100 - f(2, 28 - (1+5))
1600..1699:  100 - f(2, 28 - (1+6))
1700..1799:  100 - f(2, 28 - (1+7))
1800..1899:  100 - f(2, 28 - (1+8))
1900..1999:  100 - f(2, 28 - (1+9))

Von 2000 bis 5000 in Schritten von 1000:

2000..2999:  1000 - f(3, 28 - 2)
3000..3999:  1000 - f(3, 28 - 3)
4000..4999:  1000 - f(3, 28 - 4)

Jetzt müssen wir die Schrittweite wieder verringern, und zwar von 5000 auf 5600 in Schritten von 100, von 5600 auf 5670 in Schritten von 10 und schließlich von 5670 auf 5678 in Schritten von 1.

Ein Beispiel für eine Python-Implementierung (die inzwischen leicht optimiert und getestet wurde):

def binomial(n, k):
    if k < 0 or k > n:
        return 0
    result = 1
    for i in range(k):
        result *= n - i
        result //= i + 1
    return result

binomial_lut = [
    [1],
    [1, -1],
    [1, -2, 1],
    [1, -3, 3, -1],
    [1, -4, 6, -4, 1],
    [1, -5, 10, -10, 5, -1],
    [1, -6, 15, -20, 15, -6, 1],
    [1, -7, 21, -35, 35, -21, 7, -1],
    [1, -8, 28, -56, 70, -56, 28, -8, 1],
    [1, -9, 36, -84, 126, -126, 84, -36, 9, -1]]

def f(d, n):
    return sum(binomial_lut[d][i] * binomial(n + d - 10*i, d)
               for i in range(d + 1))

def digits(i):
    d = map(int, str(i))
    d.reverse()
    return d

def heavy(a, b):
    b += 1
    a_digits = digits(a)
    b_digits = digits(b)
    a_digits = a_digits + [0] * (len(b_digits) - len(a_digits))
    max_digits = next(i for i in range(len(a_digits) - 1, -1, -1)
                      if a_digits[i] != b_digits[i])
    a_digits = digits(a)
    count = 0
    digit = 0
    while digit < max_digits:
        while a_digits[digit] == 0:
            digit += 1
        inc = 10 ** digit
        for i in range(10 - a_digits[digit]):
            if a + inc > b:
                break
            count += inc - f(digit, 7 * len(a_digits) - sum(a_digits))
            a += inc
            a_digits = digits(a)
    while a < b:
        while digit and a_digits[digit] == b_digits[digit]:
            digit -= 1
        inc = 10 ** digit
        for i in range(b_digits[digit] - a_digits[digit]):
            count += inc - f(digit, 7 * len(a_digits) - sum(a_digits))
            a += inc
            a_digits = digits(a)
    return count

Bearbeiten : Ersetzt den Code durch eine optimierte Version (die noch hässlicher aussieht als der Originalcode). Außerdem wurden ein paar Eckfälle behoben, während ich dabei war. heavy(1234, 100000000)dauert ungefähr eine Millisekunde auf meiner Maschine.

Rekurse und verwende Permutationen.

Angenommen, wir definieren eine allgemeine Funktion, die die Werte zwischen a und b mit einer Schwere von mehr als x findet:

heavy_decimal_count(a,b,x)

Bei Ihrem Beispiel von a = 8675 bis b = 8689 ist die erste Ziffer 8, also werfen Sie sie weg - die Antwort ist die gleiche wie bei 675 bis 689 und erneut bei 75 bis 89.

Das Durchschnittsgewicht der ersten beiden Ziffern 86 beträgt 7, sodass die verbleibenden Ziffern ein Durchschnittsgewicht von mehr als 7 benötigen, um sich zu qualifizieren. Also der Anruf

heavy_decimal_count(8675,8689,7)

ist äquivalent zu

heavy_decimal_count(75,89,7)

Unser Bereich für die (neue) erste Ziffer ist also 7 bis 8, mit diesen Möglichkeiten:

7: 5-9
8: 0-9

Für 7 benötigen wir immer noch einen Durchschnitt von mehr als 7, der nur von einer letzten Ziffer von 8 oder 9 ausgehen kann, was uns 2 mögliche Werte gibt.

Für 8 benötigen wir einen Durchschnitt von mehr als 6, was nur von einer letzten Ziffer von 7-9 kommen kann, was uns 3 mögliche Werte gibt.

2 + 3 ergibt also 5 mögliche Werte.

Was passiert ist, dass der Algorithmus mit der 4-stelligen Zahl beginnt und diese in kleinere Probleme aufteilt. Die Funktion ruft sich bei einfacheren Versionen des Problems wiederholt auf, bis sie etwas hat, das sie handhaben kann.

Vielleicht können Sie viele Kandidaten im Intervall von a bis b überspringen, indem Sie ihre "Schwere" aufsummieren.

Wenn Sie die Länge Ihrer Zahl kennen, wissen Sie, dass jede Ziffer die Schwere nur um 1 / Länge verändern kann.

Wenn Sie also mit einer Zahl beginnen, die nicht schwer ist, sollten Sie in der Lage sein, die nächste Zahl zu berechnen, die schwer ist, wenn Sie sie um eins erhöhen.

In Ihrem obigen Beispiel, das mit 8680 avg = 5,5 beginnt, was 7-5,5 = 1,5 Punkte von Ihrer Schweregrenze entfernt ist, wissen Sie, dass sich 1,5 / (1/4) = 6 Zahlen dazwischen befinden, die NICHT schwer sind.

Das sollte zum Trick!

Wie wäre es mit einer einfachen rekursiven Funktion? Zur Vereinfachung werden alle großen Zahlen mit digitsZiffern und einer minimalen Ziffernsumme von berechnet min_sum.

int count_heavy(int digits,int min_sum) {
  if (digits * 9 < min_sum)//impossible (ie, 2 digits and min_sum=19)
    return 0; //this pruning is what makes it fast

  if (min_sum <= 0)
      return pow(10,digits);//any digit will do,
      // (ie, 2 digits gives 10*10 possibilities)

  if (digits == 1)
  //recursion base
    return 10-min_sum;//only the highest digits

  //recursion step
  int count = 0;
  for (i = 0; i <= 9; i++)
  {
     //let the first digit be i, then
     count += count_heavy(digits - 1, min_sum - i);
  }
  return count;
}

count_heavy(9,7*9+1); //average of 7,thus sum is 7*9, the +1 is 'exceeds'.

Implementierte dies in Python und fand alle 9-stelligen schweren Zahlen in ~ 2 Sekunden. Ein bisschen dynamisches Programmieren könnte dies verbessern.

Dies ist eine mögliche Lösung.

public int heavy_decimal_count(int A, int B)
{
    int count = 0;                       
    for (int i = A; i <= B; i++)
    {
        char[] chrArray = i.ToString().ToCharArray();
        float sum = 0f;
        double average = 0.0f;
        for (int j = 0; j < chrArray.Length; j++)
        {
            sum = sum + (chrArray[j] - '0');                   
        }
        average = sum / chrArray.Length;                
        if (average > 7)
            count++;
    }
    return count;
}

C, für Intervall [a, b] ist es O (ba)

c(n,s,j){return n?c(n/10,s+n%10,j+1):s>7*j;}

HeftyDecimalCount(a,b){int r; for(r=0;a<=b;++a)r+=c(a,0,0); return r;}

//die Übung

main()
{
 printf("[9480,9489]=%d\n", HeftyDecimalCount(9480,9489));
 printf("[0,9489000]=%d\n", HeftyDecimalCount(9480,9489000));
 return 0;
}

//die Ergebnisse

//[9480,9489]=2
//[0,9489000]=66575