Программа Javascript для подсчета вращений, кратных 4
Учитывая большое положительное число в виде строки, подсчитайте все вращения данного числа, которые делятся на 4.
Примеры:
Input: 8 Output: 1 Input: 20 Output: 1 Rotation: 20 is divisible by 4 02 is not divisible by 4 Input : 13502 Output : 0 No rotation is divisible by 4 Input : 43292816 Output : 5 5 rotations are : 43292816, 16432928, 81643292 92816432, 32928164
Для больших чисел трудно вращать и делить каждое число на 4. Поэтому используется свойство «делимость на 4», которое говорит, что число делится на 4, если последние 2 цифры числа делятся на 4. Здесь мы делаем на самом деле не поворачиваем число и не проверяем последние 2 цифры на делимость, вместо этого мы считаем последовательные пары (по кругу), которые делятся на 4.
Иллюстрация:
Consider a number 928160 Its rotations are 928160, 092816, 609281, 160928, 816092, 281609. Now form pairs from the original number 928160 as mentioned in the approach. Pairs: (9,2), (2,8), (8,1), (1,6), (6,0), (0,9) We can observe that the 2-digit number formed by the these pairs, i.e., 92, 28, 81, 16, 60, 09, are present in the last 2 digits of some rotation. Thus, checking divisibility of these pairs gives the required number of rotations. Note: A single digit number can directly be checked for divisibility.
Ниже приведена реализация подхода.
Выход:
Rotations: 2
Временная сложность: O(n), где n — количество цифр во входном числе.
Вспомогательное пространство: O(1)
Пожалуйста, обратитесь к полной статье о количестве оборотов, кратных 4, для получения более подробной информации!