Подсчет цифры 2 в диапазоне

Решение

Анализ задачи

Нужно подсчитать количество цифры 2 во всех числах от 0 до n (включительно). Это классическая задача на логику и оптимизацию.

Пример для n=25:

• Числа содержащие 2: 2, 12, 20, 21, 22, 23, 24, 25
• Количество двоек: 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 = 9

Решение 1: Простой перебор (для небольших n)

def countDigit2(n: int) -> int:
    '''
    Простой подход - перебираем все числа и считаем двойки.
    
    Временная сложность: O(n * log n) - n чисел, каждое проверяем за log n
    Пространственная сложность: O(1)
    '''
    count = 0
    for i in range(n + 1):
        count += str(i).count('2')
    return count

Преимущества:

• Очень просто понять
• Работает правильно для всех случаев

Недостатки:

• Медленно для больших n (например, n = 10^9)
• Требует преобразований в строку

Решение 2: Оптимизированный перебор

def countDigit2(n: int) -> int:
    '''
    Оптимизированный перебор - считаем цифры без преобразования в строку.
    
    Временная сложность: O(n * log n)
    Пространственная сложность: O(1)
    '''
    count = 0
    for i in range(n + 1):
        num = i
        while num > 0:
            if num % 10 == 2:
                count += 1
            num //= 10
    return count

Пример для n=25:

i=0:   нет двоек
i=2:   2 % 10 = 2 → count = 1
i=12:  12 % 10 = 2 → count = 2
i=20:  20 % 10 = 0, 2 % 10 = 2 → count = 3
i=21:  21 % 10 = 1, 2 % 10 = 2 → count = 4
i=22:  22 % 10 = 2, 2 % 10 = 2 → count = 6 (две двойки!)
...

Решение 3: Оптимальный подход O(log n) - математический

def countDigit2(n: int) -> int:
    '''
    Подсчитываем двойки по позициям (единицы, десятки, сотни...).
    Очень эффективно для больших n.
    
    Временная сложность: O(log n)
    Пространственная сложность: O(1)
    '''
    if n < 2:
        return 0
    
    count = 0
    factor = 1  # 10^0, 10^1, 10^2...
    
    while factor <= n:
        # Разделяем число на две части: выше и ниже текущей позиции
        higher = n // (factor * 10)
        lower = n % factor
        current = (n // factor) % 10
        
        if current == 2:
            # Если текущая цифра = 2, то считаем все комбинации ниже
            count += higher * factor + (lower + 1)
        elif current > 2:
            # Если текущая цифра > 2, то целая группа выше
            count += (higher + 1) * factor
        else:  # current < 2
            # Если текущая цифра < 2, то частичная группа выше
            count += higher * factor
        
        factor *= 10
    
    return count

Пример для n=25:

factor=1 (единицы):
  higher = 25 // 10 = 2
  lower = 25 % 1 = 0
  current = (25 // 1) % 10 = 5
  current > 2 → count += (2 + 1) * 1 = 3
  
factor=10 (десятки):
  higher = 25 // 100 = 0
  lower = 25 % 10 = 5
  current = (25 // 10) % 10 = 2
  current == 2 → count += 0 * 10 + (5 + 1) = 6
  
Итого: 3 + 6 = 9 ✓

Сравнение подходов

Тестовые случаи

assert countDigit2(0) == 0    # 0 не содержит 2
assert countDigit2(1) == 0    # 0,1 не содержат 2
assert countDigit2(2) == 1    # 2
assert countDigit2(12) == 2   # 2, 12
assert countDigit2(25) == 9   # 2,12,20,21,22,23,24,25
assert countDigit2(100) == 20 # Включаем числа 2..99
assert countDigit2(1000) == 300 # Сложный случай

Рекомендация для QA Automation

При тестировании функции проверяйте:

1. Граничные значения:

   • n = 0, 1 (нет двоек)
   • n = 2 (первая двойка)

2. Степени 10:

   • n = 10, 100, 1000
   • Особые случаи у границ

3. Числа содержащие несколько двоек:

   • n = 22 (две двойки в одном числе)
   • n = 222 (три двойки)

4. Производительность:

   • Простой подход: n = 10^6 (должно быть быстро)
   • Математический: n = 10^9 (мгновенно)

5. Правильность:

   • Вручную считайте для малых n (0-30)
   • Используйте оба алгоритма для больших n

Финальная рекомендация

На собеседовании:

1. Начните с простого подхода - string counting
2. Обсудите сложность - O(n * log n)
3. Предложите оптимизацию - математический подход O(log n)
4. Объясните математику - как работает по позициям
5. Обсудите trade-offs - простота vs производительность

Для production кода - используйте простой подход O(n * log n) для n < 10^7, математический для больших значений.