Problème à résoudre

Déterminer le nombre de fois que le chiffre 1 apparaît entre 1 et un nombre donné n, puis entre 100 et 1300. Par exemple, entre 1 et 13, il y a 6 occurrences du chiffre 1 (1, 10, 11, 12, 13). Pour les valeurs plus grandes, il faut une méthode efficace pour compter rapidement le nombre d'occurrences du chiffre 1.

Calculer

function countOnes() { const n = parseInt(document.getElementById('n').value); let count = 0;

for (let i = 1; i <= n; i++) { count += i.toString().split('').filter(digit => digit === '1').length; }

document.getElementById('result').innerText = Le chiffre 1 apparaît ${count} fois.; }

Méthodes de solution

Méthode par itération brute

class Solution {
    public int countDigitOne(int n) {
        if (n <= 0) {
            return 0;
        }
        int count = 0;
        for (int i = 1; i <= n; i++) {
            int num = i;
            while (num > 0) {
                if (num % 10 == 1) { // Vérifie si la dernière cifre est 1
                    count++;
                }
                num /= 10; // Supprime la dernière cifre
            }
        }
        return count;
    }
}

Cette approche brute est inefficace pour de grands nombres car elle nécessite une itération complète pour chaque chiffre jusqu'à n.

Méthode récursive

La méthode récursive divise le problème en deux parties : le nombre de fois que 1 apparaît dans les chiffres inférieurs à 10^k et le nombre de fois qu'il apparaît dans les chiffres multiples de 10^k.

class Solution {
    public int countDigitOne(int n) {
        if (n <= 0) return 0;
        if (n < 10) return 1; // De 1 à 9, il y a seulement 1 occurrence du chiffre 1

        String str = String.valueOf(n);
        int len = str.length();
        int firstDigit = str.charAt(0) - '0'; // Récupère la première cifre
        int remainder = n % (int)Math.pow(10, len - 1); // Récupère le reste après la première cifre
        int power = (int)Math.pow(10, len - 2); // Calcul le facteur de poids

        int countFirstDigit = 0;
        // Compte le nombre de fois que 1 apparaît comme première cifre
        if (firstDigit > 1) {
            countFirstDigit = (int)Math.pow(10, len - 1);
        } else if (firstDigit == 1) {
            countFirstDigit = remainder + 1;
        }
        // Compte le nombre de fois que 1 apparaît dans les autres chiffres
        int countOtherDigits = firstDigit * (len - 1) * (int)Math.pow(10, len - 2);
        // Calcule récursivement le nombre de fois que 1 apparaît dans le reste
        int countRemainder = countDigitOne(remainder);

        return countFirstDigit + countOtherDigits + countRemainder;
    }
}

• Compleixté temporelle : O(log n). La profondeur de la récursion est proportionnelle au nombre de chiffres de n.
• Complexité spatiale : O(log n). La profondeur de la pile d'appels est égale à la profondeur de la récursion.

Méthode basée sur le compte des chiffers

Cette méthode utilise des formules mathématiques pour calculer directement le nombre de fois que 1 apparaît à chaque position (unités, dizaines, centaines, etc.).

Pour chaque position, nous pouvons diviser le nombre en trois parties :

• Haute partie (high) : les chiffres situés avant la position actuelle
• Chiffre actuel (cur) : le chiffre situé à la position actuelle
• Basse partie (low) : les chiffres situés après la position actuellle
• Facteur de poids (digit) : indique la valeur numérique de la position actuelle (ex: unités = 1, dizaines = 10, centaines = 100)

Selon la valeur du chiffre actuel cur, nous avons trois cas possibles :

1. cur == 0 : si le chiffre actuel est 0, le nombre de fois que 1 apparaît à cette position est déterminé par la haute partie, selon la formule high * digit.
2. cur == 1 : si le chiffre actuel est 1, le nombre de fois que 1 apparaît est déterminé par la somme de la haute partie, de la basse partie et de 1, selon la formule high * digit + low + 1.
3. cur > 1 : si le chiffre actuel est supérieur à 1, le nombre de fois que 1 apparaît est déterminé par la haute partie augmentée de 1, selon la formule (high + 1) * digit.

class Solution {
    public int countDigitOne(int n) {
        if (n <= 0) return 0;
        int count = 0;
        long digit = 1; // Facteur de poids, commence par les unités
        int high = n / 10; // Haute partie
        int cur = n % 10; // Chiffre actuel
        int low = 0; // Basse partie

        while (high != 0 || cur != 0) {
            if (cur == 0) {
                count += high * digit;
            } else if (cur == 1) {
                count += high * digit + low + 1;
            } else {
                count += (high + 1) * digit;
            }
            // Met à jour la basse partie, le chiffre actuel, la haute partie et le facteur de poids
            low += cur * digit;
            cur = high % 10;
            high = high / 10;
            digit *= 10;
        }
        return count;
    }
}

• Complexité temporelle : O(log n) : Le nombre d'itérations est proportionnel au nombre de chiffres de n.
• Complexité spatiale : O(1) :