CODEWITHSUNDEEP
c++algorithm
minhperry
minhperry

Reputation: 129

Ways to go from a number to 0 the fastest way

So, I have a homework like this:

Given two number n and k that can reach the long long limit, we do such operation:

Find the smallest number of operations to go from n to 0.

This is my solution

#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;
    }
}

This solution is O(n/k) I think?

But I think that n and k could be extremely big, and thus the program could exceed the time limit of 1s. Is there any better way to do this?

Edit 1: I use ll for it to be shorter

Upvotes: 0

Views: 395

Answers (2)

Prune
Prune

Reputation: 77860

This can be done with an even simpler main program.

Convert n to base k. Let d be the number of digits in this number. To get to 0, you will divide by k (d-1) times. The number of times you subtract 1 is the digital sum of this number.

For instance, consider n=314, k=3.

314 in base 3 is 102122. This has 6 digits; the digital sum is 8. You will have 6-1+8 steps ... 13 steps to 0.

Use your C++ packages to convert to the new base, convert the digits to integers, and do the array sum. This pushes all the shift-count work into module methods.

Granted this won't work for weird values of k, but you can also steal available conversion packages instead of writing your own.

Upvotes: 1

Quimby
Quimby

Reputation: 19213

The algorithm can be improved given these observations:

  1. If n<k then k|(n-m) will never hold for any positive m. So the answer is n steps.
  2. If (k|n) does not hold then the biggest number m, m<n for which it does is n - (n%k). So it takes n%k steps until (k|m) holds again.

Actually all that you need is to keep doing division with remainder using std::div (or rely on compiler to optimize) and increase steps by remainder+1.

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

Upvotes: 8

Related Questions