Подсчитайте количество нулей в представлении числа по базе K

По заданному числу N задача состоит в том, чтобы найти количество нулей в представлении данного числа по основанию K , где K > 1 .

Примеры:

Input: N = 10, K = 3
Output: 1
Explanation: Base 3 representation of 10 is 101. 
Hence the number of 0’s in 101 is 1.

Input: N = 8, K = 2
Output: 3
Explanation: Base 2 representation of 8 is 1000. 
Hence the number of 0’s in 1000 is 3.

Подход: Эту проблему можно решить, преобразовав число в базовую форму K.
Псевдокод для преобразования числа N по основанию 10 в основание K :

allDigits = “”
While N > 0:
       digit = N%k
       allDigits.append(digit)
       N /= k
number_in_base_K = reversed(allDigits)

Выполните шаги, указанные ниже, чтобы реализовать подход:

• Начните формировать базовое число K , как показано в приведенном выше псевдокоде.
• Вместо того, чтобы формировать число, только проверяйте в каждом проходе цикла, является ли текущая формируемая цифра 0 или нет.
• Возвращает общее количество 0s.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(1)
Вспомогательное пространство: О(1)