C++程序 计算可被10整除的旋转次数
给定一个数字 N ,任务是计算旋转给定数字后可被10整除的次数。
示例:
输入: N = 10203
输出: 2
解释:
给定数字可以有5种旋转方式:02031、20310、03102、31020和10203。在这些数字中,只有20310和31020可被10整除。因此,输出为2。
输入: N = 135
输出: 0
Naive Approach: 该问题的朴素方法是形成所有可能的旋转。已知一个大小为 K 的数字,其旋转次数为 N 为 K 。因此,找到所有旋转并对于每个旋转检查数字是否可以被10整除。该方法的时间复杂度为二次方。
Efficient Approach: 高效的方法在于检查一个数字是否可被10整除的概念,我们仅需检查最后一位数字是否为0。因此,基本想法是简单地遍历给定的数字并找到0的数量。如果0的数量为 F ,那么显然有 F 个旋转中,给定数字 N 末尾有0。
以下是上述方法的实现:
// C++ implementation to find the
// count of rotations which are
// divisible by 10
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of
// all the rotations which are
// divisible by 10.
int countRotation(int n)
{
int count = 0;
// Loop to iterate through the
// number
do {
int digit = n % 10;
// If the last digit is 0,
// then increment the count
if (digit == 0)
count++;
n = n / 10;
} while (n != 0);
return count;
}
// Driver code
int main()
{
int n = 10203;
cout << countRotation(n);
}
输出:
2
时间复杂度: O(log 10 N) ,其中N为数字长度。
辅助空间: O(1)