Сложность: hard
Дано целое число n, посчитайте общее количество единиц, встречающихся во всех неотрицательных числах, меньших или равных n.
Пример:
Input: n = 13
Output: 6
👨💻 Алгоритм:
1⃣Итерация по степеням 10: Итеративно увеличивайте значение i от 1 до n, увеличивая i в 10 раз на каждом шаге. Это позволяет анализировать каждую цифру числа n.
2⃣Подсчет групповых единиц: Для каждой итерации добавляйте (n / (i * 10)) * i к счетчику countr, что представляет собой количество единиц, встречающихся в группах размера i после каждого интервала (i * 10).
3⃣Добавление дополнительных единиц: Для каждой итерации добавляйте min(max((n % (i * 10)) - i + 1, 0), i) к счетчику countr, что представляет собой дополнительные единицы, зависящие от цифры на позиции i.
😎 Решение:
int countDigitOne(int n) {
int countr = 0;
for (long long i = 1; i <= n; i *= 10) {
long long divider = i * 10;
countr += (n / divider) * i + std::min(std::max(n % divider - i + 1, 0LL), i);
}
return countr;
}Ставь 👍 и забирай 📚 Базу знаний