Disons que nous avons un entier non négatif qui est «lourd» (c'est-à-dire «lourd») si sa valeur numérique moyenne est supérieure à 7.

Le numéro 6959 est "lourd" car:

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

Le numéro 1234 ne l'est pas, car:

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

Écrivez une fonction, dans n'importe quelle langue,

HeftyDecimalCount(a, b)

qui, lorsqu'ils sont fournis, deux entiers positifs a et b renvoient un entier indiquant le nombre d'entiers "lourds" dans l'intervalle [a..b], inclus.

Par exemple, étant donné a = 9480 et 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

Deux des nombres de cette plage sont "lourds" et donc la fonction devrait retourner 2.

Quelques directives:

• supposons que ni a ni b ne dépasse 200 000 000.
• une solution n-carré fonctionnera, mais sera lente - quel est le plus rapide que nous pouvons résoudre cela?

Le problème peut être résolu dans O (polylog (b)).

Nous définissons f(d, n)comme le nombre d'entiers jusqu'à d chiffres décimaux avec une somme de chiffres inférieure ou égale à n. On voit que cette fonction est donnée par la formule

Dérivons cette fonction, en commençant par quelque chose de plus simple.

La fonction h compte le nombre de façons de choisir d - 1 éléments dans un multi-ensemble contenant n + 1 éléments différents. C'est aussi le nombre de façons de partitionner n en d cases, ce qui peut être facilement vu en construisant d - 1 clôtures autour de n unités et en résumant chaque section séparée. Exemple pour 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

Donc, h compte tous les nombres ayant une somme de n et d chiffres. Sauf que cela ne fonctionne que pour n inférieur à 10, car les chiffres sont limités à 0 - 9. Afin de résoudre ce problème pour les valeurs 10 à 19, nous devons soustraire le nombre de partitions ayant un bac avec un nombre supérieur à 9, que j'appellerai désormais des bacs survolés.

Ce terme peut être calculé en réutilisant h de la manière suivante. Nous comptons le nombre de façons de partitionner n - 10, puis choisissons l'un des casiers dans lequel placer les 10, ce qui entraîne le nombre de partitions ayant un casier débordé. Le résultat est la fonction préliminaire suivante.

Nous continuons de cette façon pour n inférieur ou égal à 29, en comptant toutes les façons de partitionner n - 20, puis en choisissant 2 bacs dans lesquels nous mettons les 10, comptant ainsi le nombre de partitions contenant 2 bacs débordés.

Mais à ce stade, nous devons être prudents, car nous avons déjà compté les partitions ayant 2 bacs survolés dans le terme précédent. Non seulement cela, mais en fait, nous les avons comptés deux fois. Prenons un exemple et examinons la partition (10,0,11) avec la somme 21. Dans le terme précédent, nous avons soustrait 10, calculé toutes les partitions des 11 restantes et placé les 10 dans l'une des 3 cases. Mais cette partition particulière peut être atteinte de deux manières:

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

Étant donné que nous avons également compté ces partitions une fois au premier trimestre, le nombre total de partitions avec 2 cases dépassées s'élève à 1 - 2 = -1, nous devons donc les compter à nouveau en ajoutant le terme suivant.

En y réfléchissant un peu plus, nous découvrons bientôt que le nombre de fois qu'une partition avec un nombre spécifique de bacs survolés est comptée dans un terme spécifique peut être exprimée par le tableau suivant (la colonne i représente le terme i, les rangées j partitions avec j survolé) bacs).

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

Oui, c'est le triangle de Pascals. Le seul décompte qui nous intéresse est celui de la première ligne / colonne, c'est-à-dire le nombre de partitions avec zéro bacs débordés. Et puisque la somme alternée de chaque ligne mais la première est égale à 0 (par exemple 1 - 4 + 6 - 4 + 1 = 0), c'est ainsi que nous nous en débarrassons et arrivons à l'avant-dernière formule.

Cette fonction compte tous les nombres avec d chiffres ayant une somme de n.

Maintenant, qu'en est-il des nombres dont la somme des chiffres est inférieure à n? Nous pouvons utiliser une récurrence standard pour les binômes plus un argument inductif, pour montrer que

compte le nombre de partitions avec somme numérique au plus n. Et de ce f peut être dérivé en utilisant les mêmes arguments que pour g.

En utilisant cette formule, nous pouvons par exemple trouver le nombre de nombres lourds dans l'intervalle de 8000 à 8999 car 1000 - f(3, 20), car il y a des milliers de nombres dans cet intervalle, et nous devons soustraire le nombre de nombres avec une somme de chiffres inférieure ou égale à 28 tout en tenant compte du fait que le premier chiffre contribue déjà 8 à la somme des chiffres.

Comme exemple plus complexe, regardons le nombre de nombres lourds dans l'intervalle 1234..5678. Nous pouvons d'abord passer de 1234 à 1240 par étapes de 1. Ensuite, nous passons de 1240 à 1300 par étapes de 10. La formule ci-dessus nous donne le nombre de nombres lourds dans chacun de ces intervalles:

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))

On passe maintenant de 1300 à 2000 par pas de 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))

De 2000 à 5000 par pas de 1000:

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

Nous devons maintenant réduire à nouveau la taille des pas, en passant de 5000 à 5600 par pas de 100, de 5600 à 5670 par pas de 10 et enfin de 5670 à 5678 par pas de 1.

Un exemple d'implémentation Python (qui a reçu entre-temps de légères optimisations et tests):

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

Edit : Remplacé le code par une version optimisée (qui semble encore plus moche que le code d'origine). J'ai également corrigé quelques cas d'angle pendant que j'y étais. heavy(1234, 100000000)prend environ une milliseconde sur ma machine.

Réexaminez et utilisez les permutations.

Supposons que nous définissions une fonction générale qui trouve les valeurs entre a et b avec une lourdeur supérieure à x:

heavy_decimal_count(a,b,x)

Avec votre exemple de a = 8675 à b = 8689, le premier chiffre est 8, alors jetez-le - la réponse sera la même que 675 à 689, et encore de 75 à 89.

Le poids moyen des deux premiers chiffres 86 est 7, donc les chiffres restants ont besoin d'un poids moyen supérieur à 7 pour se qualifier. Ainsi, l'appel

heavy_decimal_count(8675,8689,7)

est équivalent à

heavy_decimal_count(75,89,7)

Notre plage pour le (nouveau) premier chiffre est donc de 7 à 8, avec ces possibilités:

7: 5-9
8: 0-9

Pour 7, nous avons encore besoin d'une moyenne de plus de 7, qui ne peut provenir que d'un chiffre final de 8 ou 9, ce qui nous donne 2 valeurs possibles.

Pour 8, nous avons besoin d'une moyenne de plus de 6, qui ne peut provenir que d'un chiffre final de 7-9, ce qui nous donne 3 valeurs possibles.

Donc, 2 + 3 donne 5 valeurs possibles.

Ce qui se passe, c'est que l'algorithme commence par le nombre à 4 chiffres et le divise en problèmes plus petits. La fonction s'appellerait à plusieurs reprises avec des versions plus faciles du problème jusqu'à ce qu'elle ait quelque chose qu'elle puisse gérer.

Vous pouvez peut-être ignorer de nombreux candidats dans l'intervalle de a à b en accumulant leur "lourdeur".

si vous connaissez la longueur de votre numéro, vous savez que chaque chiffre ne peut changer la lourdeur que de 1 / longueur.

Donc, si vous commencez avec un nombre qui n'est pas lourd, vous devriez pouvoir calculer le nombre suivant qui sera lourd, si vous les augmentez d'un.

Dans votre exemple ci-dessus à partir de 8680 avg = 5,5, qui est à 7-5,5 = 1,5 point de votre frontière de lourdeur, vous savez qu'il y a 1,5 / (1/4) = 6 nombres entre les deux, qui ne sont PAS lourds.

Cela devrait faire l'affaire!

Que diriez-vous d'une simple fonction récursive? Pour simplifier les choses, il calcule tous les nombres lourds avec des digitschiffres et une somme minimale de chiffres 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'.

Implémenté cela en python et il a trouvé tous les nombres lourds à 9 chiffres en ~ 2 secondes. Un peu de programmation dynamique pourrait améliorer cela.

C'est une solution possible.

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, pour l'intervalle [a, b] c'est 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;}

//l'exercice

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

//Les resultats

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