Программа Javascript для подсчета вращений, кратных 8
Учитывая большое положительное число в виде строки, подсчитайте все вращения данного числа, которые делятся на 8.
Примеры:
Input: 8 Output: 1 Input: 40 Output: 1 Rotation: 40 is divisible by 8 04 is not divisible by 8 Input : 13502 Output : 0 No rotation is divisible by 8 Input : 43262488612 Output : 4
Подход: для больших чисел трудно вращать и делить каждое число на 8. Поэтому используется свойство «делимость на 8», которое говорит, что число делится на 8, если последние 3 цифры числа делятся на 8. Здесь мы на самом деле не поворачиваем число и не проверяем последние 8 цифр на делимость, вместо этого мы подсчитываем последовательную последовательность из 3 цифр (по кругу), которые делятся на 8.
Иллюстрация:
Consider a number 928160 Its rotations are 928160, 092816, 609281, 160928, 816092, 281609. Now form consecutive sequence of 3-digits from the original number 928160 as mentioned in the approach. 3-digit: (9, 2, 8), (2, 8, 1), (8, 1, 6), (1, 6, 0),(6, 0, 9), (0, 9, 2) We can observe that the 3-digit number formed by the these sets, i.e., 928, 281, 816, 160, 609, 092, are present in the last 3 digits of some rotation. Thus, checking divisibility of these 3-digit numbers gives the required number of rotations.
Выход:
Rotations: 4
Временная сложность: O(n), где n — количество цифр во входном числе.
Вспомогательное пространство: O(1)
Пожалуйста, обратитесь к полной статье о количестве оборотов, кратных 8, для получения более подробной информации!