Compter le nombre d'occurrences de 0 des entiers de 1 à N

Comment saurez-vous efficacement compter le nombre d'occurrences de 0 dans la représentation décimale des entiers de 1 à N?

e.g. The number of 0's from 1 to 105 is 16. How?

10,20,30,40,50,60,70,80,90,100,101,102,103,104,105

Compter le nombre de ' 0 ' & vous le trouverez à 16.

Évidemment, une approche par force brute ne sera pas apprécié. Vous devez venir avec une approche qui ne dépend pas de "Combien de nombres sont comprises entre 1 à N".
Peut-on juste faire en voyant une sorte de modèle?

Ne peut-on étendre le la logique compilés ici de travailler pour ce problème?

Je pensais que vous n'étiez pas censés fuite de ces questions après une interview 😉
C'est clairement proportionnelle à n^2, si juste qu'il ne la force brute jusqu'à 10k 100k pour en déduire une constante et vous avez terminé.
il est plus probable dans l'ordre de N log N je dirais.
J'aime ces sortes de questions. Chance d'une application pratique de l'algorithme à l'extérieur de la salle de classe 0.00000000000000000000000000001%.
Pour faire une distribution de chiffres dans une série, il aide à les compter. en.wikipedia.org/wiki/Benford's_law

OriginalL'auteur Green goblin | 2012-08-09

algorithm c math

17

Mise À Jour De Réponse

Ma réponse a été simple à comprendre mais difficile à code. Voici quelque chose qui est plus simple à code. C'est un straight-forward non-récursive solution qui fonctionne en comptant le nombre de façons de zéros peuvent apparaître dans chaque position.

Par exemple:

x <= 1234. Combien de nombres sont de la forme suivante?

x = ??0?

Il y a 12 possibilités pour l' "des centaines ou plus" (1,2, ..., 12). Il doit y avoir un zéro. Ensuite, il y a 10 possibilités pour le dernier chiffre. Cela donne 12 * 10 = 120 numéros contenant un 0 à la troisième chiffre.

La solution pour la plage (1 à 1234) est donc:
- ?0??: 1 * 100 = 100
- ??0?: 12 * 10 = 120
- ???0: 123
- Total = 343
Mais une exception est si n contient un chiffre zéro. Considérons le cas suivant:

x <= 12034. Combien de nombres sont de la forme suivante?

x = ??0??

Nous avons 12 façons de choisir les "milliers ou plus". Pour 1, 2, ... 11 nous pouvons choisir deux derniers chiffres (ce qui donne 11 * 100 possibilités). Mais si nous commençons avec 12 on ne peut choisir un nombre entre 00 et 34 pour les deux derniers chiffres. Nous obtenons donc 11 * 100 + 35 possibilités tout à fait.

Voici une implémentation de cet algorithme (écrit en Python, mais d'une manière qui devrait être facile de port à C):
```
def countZeros(n):
    result = 0
    i = 1

    while True:
        b, c = divmod(n, i)
        a, b = divmod(b, 10)

        if a == 0:
            return result

        if b == 0:
            result += (a - 1) * i + c + 1
        else:
            result += a * i

        i *= 10
```
Pour 1 à 999, votre "un traitement spécial pour la condition de fin" couvre 90% de la gamme (de 100 à 999). Ce n'est pas une très bonne réponse...
Je pense que vous avez mal interprété la partie. La règle est de diviser le nombre de plages avec le même nombre de chiffres, [1,999] devient ([1,9],[10,99],[100,999]), et ensuite, pour chaque segment de vous faire (haut-bas)*(longueur-1)/10, et les additionner. "Un traitement spécial pour la condition de fin" serait si, au lieu de [1,999] nous avons eu quelque chose comme [1,1234], où [1000,1234] ne rentre pas dans le modèle. C'est seulement cette dernière partie qui a besoin d'un traitement spécial.
Oui, je pensais (1,666) ou quelque chose, mais j'ai décidé d'aller le tout pour le tout et est allé trop loin.
OK, donc le code de telle manière qu'il nous est possible de le comparer à d'autres solutions 🙂
Maintenant que vous avez bien fourni le code et débogué, je suis de retirer mon downvote. Je pense toujours que la formulation récursive est plus simple, mais je suis d'accord que cela fonctionne. P. S. @drewk "attentes" sont peut-être mieux disant "donner la bonne réponse"

OriginalL'auteur
9

Je suggère d'adapter cet algorithme de base 2 en base 10:

Nombre de 1s dans le complément à deux représentations binaires des nombres entiers dans une gamme

L'résultant de l'algorithme est O(log N).

L'approche est d'écrire une simple fonction récursive count(n) qui compte le nombre de zéros de 1 à n.

L'observation essentielle est que si N se termine dans 9, par exemple:
```
123456789
```
Vous pouvez placer les nombres de 0 à N en 10 groupes de taille égale. Le groupe 0 est les nombres se terminant par 0. Le groupe 1 est le nombre se terminant par 1. Le groupe 2, les nombres se terminant par 2. Et ainsi de suite, tout le chemin à travers le groupe de 9, qui est tous les numéros se terminant par 9.

Chaque groupe à l'exception du groupe 0 contribue count(N/10) zéro chiffres au total, car aucun d'entre eux fin à zéro. Groupe 0 contribue count(N/10) (qui comprend tous les chiffres, sauf le dernier), plus N/10 (qui compte les zéros de la finale chiffres).

Puisque nous sommes allant de 1 à N au lieu de 0 à N, cette logique s'effondre pour un seul chiffre N, donc nous avons juste la poignée que comme un cas particulier.

[mise à jour]

Ce que le diable, nous allons généraliser et de définir count(n, d) combien de fois le chiffre d apparaît parmi les nombres de 1 à n.
```
/* Count how many d's occur in a single n */
unsigned
popcount(unsigned n, unsigned d) {
  int result = 0;
  while (n != 0) {
    result += ((n%10) == d);
    n /= 10;
  }
  return result;
}

/* Compute how many d's occur all numbers from 1 to n */
unsigned
count(unsigned n, unsigned d) {
  /* Special case single-digit n */
  if (n < 10) return (d > 0 && n >= d);

  /* If n does not end in 9, recurse until it does */
  if ((n % 10) != 9) return popcount(n, d) + count(n-1, d);

  return 10*count(n/10, d) + (n/10) + (d > 0);
}
```
La laideur pour le cas n < 10 vient de nouveau de la gamme allant de 1 à n au lieu de 0 à n... Pour tout à un seul chiffre n supérieure ou égale à d, le nombre est 1, sauf lorsque d est zéro.

De la conversion de cette solution à un non-récursive boucle (a) est trivial, (b) inutiles, et (c) laissé comme exercice pour le lecteur.

[Mise à jour 2]

La finale (d > 0) terme vient aussi de la gamme allant de 1 à n au lieu de 0 à n. Lorsque n se termine dans 9, combien de nombres entre 1 et n inclusive ont dernier chiffre d? Eh bien, quand d est égale à zéro, la réponse est n/10; quand d est non-nul, il est l'un plus que cela, puisqu'il comprend la valeur d lui-même.

Par exemple, si n est de 19 et d est 0, il n'existe qu'un petit nombre se terminant par 0 (10). Mais si n est de 19 et d est de 2, il y a deux plus petits nombres se terminant par 2 (c'est à dire 2 et 12).

Grâce à @Chan d'avoir signalé ce bug dans les commentaires; j'ai fixé dans le code.

+1: C'est très simple et correcte.
J'ai posté une solution qui, je crois, quelque chose de semblable à ce que vous avez suggéré. Je suis aux prises avec la généralisation ma solution. Pouvez vous s'il vous plaît m'aider avec ça ? Merci
Avez-vous testé votre solution? Pour n = 20 avec d = 2, il y a 3 2 (2, 12, 20), mais votre solution ne produit que de 2.
En effet, j'ai eu un bug à chaque fois que d est non nul. Fixe; merci.
Vous êtes les bienvenus 😉

OriginalL'auteur
4

Laisser Z(n) = #zero digits in numbers 0 <= k < n. Évidemment, Z(0) = 0.

Si n = 10*k + r, 0 <= r <= 9, tous les 10*k numéros de 10*j + s, 0 <= j < k, 0 <= s <= 9 sont dans la gamme, chaque dixième dernier chiffre est 0, de sorte que la k zéros, et chaque préfixe j (tous sauf le dernier chiffre) se produit une dizaine de fois, mais il ne faut pas compter 0, de sorte que le nombre de zéros dans les préfixes est 10*(Z(k)-1).

Le nombre de zéros dans le r numéros de 10*k, ..., 10*k + (r-1) est r*number of zeros in k + (r > 0 ? 1 : 0).

Nous avons donc un O(log n) algorithme pour le calcul de Z(n)
```
unsigned long long Z(unsigned long long n)
{
    if (n == 0) {
        return 0;
    }
    if (n <= 10) {
        return 1;
    }
    unsigned long long k = n/10, r = n%10;
    unsigned long long zeros = k + 10*(Z(k)-1);
    if (r > 0) {
        zeros += r*zeroCount(k) + 1;
    }
    return zeros;
}

unsigned zeroCount(unsigned long long k)
{
    unsigned zeros = 0;
    while(k) {
        zeros += (k % 10) == 0;
        k /= 10;
    }
    return zeros;
}
```
Pour calculer le nombre pour une gamme arbitraire,
```
unsigned long long zeros_in_range(unsigned long long low, unsigned long long high)
{
    return Z(high+1) - Z(low); //beware of overflow if high is ULLONG_MAX
}
```
votre fonction Z(105) est de 26, Incorrect.
Oublié de soustraire le 0-préfixes, merci pour le heads-up.
Non, 344 est correct, Prelude> length . filter (== '0') $ [0 .. 1233] >>= show donne 344. Z(n) compte le nombre de zéros dans 0, 1, ..., n-1, donc il doit être au moins à 1 pour tous les n > 0.
C'est à partir de 0. Tous les droits.

OriginalL'auteur

La façon dont j'ai abordé ce problème:

numéros peut être dans la plage de 1 à N:

Donc, je me suis cassé la présente en plages comme ceci:

Rangle      : #Digits   :   #Zeros
1   -   9   :   1       :   0
10  -   99  :   2       :   9 (number of all the possible digits when zero is at units place=> _0 ie, 1,2,3,4,5,6,7,8,9
100 -   199 :   3       :   20 => 10 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
200 -   276 :   3       :   18 => 8 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
300 -   308 :   3       :   10 => 1 (#digits when zero is at units place) + 9 (#digits when zero is at tens place)
1000-   1008:   4       :   19 => 1 + 9 + 9

Maintenant pour toute la gamme 1 - N, je veux être en mesure de briser le nombre de ces plages et de l'utilisation de la logique ci-dessus pour calculer le nombre de zéros.

Test:

pour un nombre donné N:

- compute number of digits: len
- if len = 1 : d1: return 0
- len = 2: d2_temp: count # of digits that can possibly occur when 0 is at unit's place 
            : for e.g. 76: so numbers can be between 10 - 76: (7 - 1) + 1 = 7
         : d2: sum(d2_temp, d1)
- len = 3: return d3 : sum(d3_temp, d2)
         : compute d3_temp: 
         : for e.g. n = 308 : get digit at 10^(len-1) : loopMax 3
         : d3_temp1: count number of zeros for this loop: 1 * 100 to (loopMax -1) * 100 : (loopMax-1) * 20
         : d3_temp2: for n count (#digits when zero is at units place) + (#digits when zero is at tens place)
         : d3_temp = d3_temp1 + d3_temp2

Permet d'essayer de généraliser:

99 : sum( , )
    : d3_temp: 
    : loopMax: n = 99 : n/(10^1) : 9
    : d3_temp1: 8 : (9-1) * (10*(len-1)) : (loopMax - 1) * 10 * (len-1)
    : d3_temp2: 1 : for len, count #0s in range (loopMax * 10 * (len-1)) to n : count(90, 99)
    : d3_temp = 8 + 1
    : sum(9, 0)
    : 9

Je vais avoir quelques difficultés à procéder à partir d'ici, mais ce serait le travail.

Je pense que c'est similaire à ce que vous avez suggéré. Pouvez-vous svp m'aider à venir avec la généralisation de faire une fonction ?

OriginalL'auteur

class FindZero{

    public int findZero(int lastNumber){

        int count=1,k;
        if(lastNumber<10)
            return 0;
        else if(lastNumber==10)
            return 1;
        else{

            for(int i=11;i<=lastNumber;i++){
                k=i;
                while(k>0){

                    if(k%10==0)
                        count++;
                        k=k/10;
                }
            }
            return count;
        }
    }
    public static void main(String args[]){
        FindZero obj = new FindZero();
        System.out.println(obj.findZero(1234));
    }
}

OriginalL'auteur

Vous devez vous connecter pour publier un commentaire.