Подсчитайте базы, которые содержат установленный бит в качестве старшего бита в представлении N
Учитывая положительное целое число N , задача состоит в том, чтобы подсчитать количество различных оснований, в которых, когда представлено N , старший бит N оказывается установленным битом.
Примеры:
Input: N = 6
Output: 4
Explanation: The number 6 can be represented in 5 different bases, i.e. base 2, base 3, base 4, base 5, base 6.
- (6)10 in base 2: (110)2
- (6)10 in base 3: (20)3
- (6)10 in base 4: (12)4
- (6)10 in base 5: (11)5
- (6)10 in base 6: (10)6
The base representation for (6)10 in base 2, base 4, base 5, base 6 starts with 1. Hence, the required count of bases is 4.
Input: N = 5
Output: 4
Подход: данная проблема может быть решена путем нахождения старшего бита заданного числа N для каждого возможного основания и подсчета тех оснований, у которых старший бит равен 1 . Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте переменную, скажем, count как 0 , чтобы сохранить требуемый результат.
- Переберите диапазон [2, N], используя переменную, скажем, B , и выполните следующие шаги:
- Храните наивысшую мощность baseB требуется для представления числа N в переменной P . Этого можно легко добиться, найдя значение ( log N по основанию B ), т. е. log B (N) , усеченное до ближайшего целого числа.
- Чтобы найти значение log B (N) , используйте свойство журнала: log B (N) = log (N)/log (B)
- Сохраните старшую цифру N путем деления N на (B) P . Если он равен 1 , то увеличьте значение счетчика на 1.
- После выполнения вышеуказанных шагов выведите в качестве результата значение count .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N)
Вспомогательное пространство: O(1)