时间戳

首页 > 解决方案 > 从数字到0最快的方法

c++ - 从数字到0最快的方法

问题描述

所以，我有这样的作业：

给定两个数字n并且k可以达到long long极限，我们进行这样的操作：

找到要从n到的最小操作数0。

这是我的解决方案

#define ll long long

ll smallestSteps(ll n, ll k) {
    int steps = 0;
    if (n < k) return n;
    else if (n == k) return 2;
    else {
        while (n != 0) {
            if (n % k == 0) {
                n /= k;
                steps++;
            }
            else {
                n--;
                steps++;
            }
        }
        return (ll)steps;
    }
}

我认为这个解决方案是O(n/k)什么？

但我认为它n可能k非常大，因此程序可能会超过 1s 的时间限制。有没有更好的方法来做到这一点？

编辑1：我用ll它来缩短

标签： c++algorithm

解决方案

鉴于以下观察结果，可以改进算法：

  1. 如果n<kthenk|(n-m)将永远不会适用于任何正 m。所以答案是n步骤。
  2. 如果(k|n)不成立，那么它成立的最大数m, m<n是n - (n%k). 所以它采取n%k步骤直到 (k|m) 再次成立。

实际上，您所需要的只是继续使用余数进行除法std::div（或依靠编译器进行优化），并将步数增加余数+1。

steps=0
while(n>0)
     mod = n%k
     n = n/k
     steps+=mod + 1
return steps

推荐阅读