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)