2
\$\begingroup\$

You are given a, b and c. You need to convert a to b. You can perform following operations:

  • Multiply a by c
  • Decrease a by 2
  • Decrease a by 1

You can perform these operations in any order and any number of times. You need to find and print minimum number of steps to convert a to b.

Constraints:

  • 1 ≤ t ≤ 10⁴
  • 0 ≤ a, b, c ≤ 10⁹

Input:

First line contains number of test cases.
Next line contains three space-separated integers a, b, c.

Output:

Print minimum no. of steps as output in new line for each test case.

SAMPLE INPUT

2
3 10 2
11 6 2

SAMPLE OUTPUT

3
3

Reasoning

For test case 1:

  1. First multiply 3 with 2.
  2. Subtract 1 from 6 to get 5.
  3. Multiply 5 by 2 to get 10. So, 3 steps.

For test case 2:

  1. Subtract 2 from 11.
  2. Subtract 2 from 9.
  3. Subtract 1 from 7. So, 3 steps.

My code is taking more time than expected; it scales as O(b).

#include <iostream>
#include <queue>
#include <unordered_set>

using namespace std;

int minimumSteps(int a, int b, int c) {
    if (a == b || (a < b && c <= 1)) return 0;
    unordered_set<int> visited{a};
    queue<int> q;
    q.push(a);

    int count = 0;
    int answer = INT_MAX;
    int result = 0;
    while (!q.empty()) {
        int n = q.size();
        while (n--) {
            int current = q.front();
            cout << current << " ";
            q.pop();

            result = current * c;
            if (result == b) return min(count + 1, answer);
            if (current < b && !visited.count(result)) { 
                if (result < b) {
                    q.push(result);
                    visited.insert(result); 
                } else answer = min(answer, count + ((result - b) / 2) + ((result - b) % 2) + 1);
            } 

            int subtract[2] = { current - 2, current - 1 };
            for (int i = 0; i < 2; i++) {
                result = subtract[i];
                if (result == b) return min(count + 1, answer);
                if (result > 0 && !visited.count(result)) {
                    q.push(result);
                    visited.insert(result); 
                }
            } 
        }
        count++;
    }

    return min(answer, count);
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        int a, b, c;
        cin >> a >> b >> c;

        int result = minimumSteps(a, b, c);
        cout << "Ans: " << result << "\n";
    }

    return 0;
}
\$\endgroup\$
0

3 Answers 3

Reset to default
3
\$\begingroup\$

As usual with these problems, they're more about math than programming. You often have to solve it with pen and paper before you write a single line of code, otherwise you will never meet the performance target.

In this particular problem, there are three key elements:

  1. Run the algorithm in reverse. The operations are now "divide b by c", "add 1 to b" and "add 2 to b"

  2. If b > a, you have to divide at some point. It is always better to divide first, then increment. You can easily prove this.

  3. If you have to increment repeatedly, you don't actually have to do that. You can calculate the number of steps directly. You already figured this out on your own.

The program could look like this:

int minimumSteps(int a, int b, int c) {
    int steps = 0;
    while (b > a) {
        // Increment b until divisible by c, then divide by c. This is
        // equivalent to b = ceiling(b/c). Calculate how often you had
        // to increment it, plus one for the division itself.
        int q = (b + c - 1) / c;
        steps += (q * c - b + 1) / 2 + 1;
        b = q;
    }
    // Now that b is too small, calculate how often you have to
    // increment it. Equivalent to ceiling((a-b)/2).
    steps += (a - b + 1) / 2;
    return steps;
}
\$\endgroup\$
2
\$\begingroup\$

This is a very nice task to practice some TDD.

Write tests first. Let them fail. Implement the function to make the tests green. Refactor and repeat.

Stop when you're happy with the result and you can think of no more edge cases that you haven't covered by tests.

A simple test program using just assert could look like this

#include <cassert>

int main()
{
    assert(3 == minimumSteps(3, 10, 2));
    assert(3 == minimumSteps(11, 6, 2));
    assert(2 == minimumSteps(5, 12, 3));

    return 0;
}

I am assuming you have no experience with unit testing, in practice you should reach out for a proper testing framework, but hopefully assert is good enough to show the point and get your started. A proper framework can give you, among other things, also code coverage (tells which lines of tested code actually got executed during the test run) which helps you find cases that you don't have tests for or find lines of code that are not needed for the function to work and so can be eliminated.

To test that the actual output binary program works you would have to write similar tests but from outside (ie. in bash).

\$\endgroup\$
1
\$\begingroup\$

Please don't using namespace std;. It discards useful information and makes the code harder to read. In extreme cases, it can even introduce bugs.

Since a, b, and c cannot be negative, we could be using unsigned types for their values. int is certainly the wrong type because its maximum value could be as small as 32767. I recommend using std::uint_fast32_t to cover the range 0 to 1000000000 as required by the problem statement.

The output does not conform to the problem statement - it does not ask for the number to be preceded by Ans: , so we should omit that.

We optimistically assume that >> succeeds. Good code should be more robust when reading user-supplied data.

The algorithm is very inefficient. We don't need this kind of brute-force searching, as we just need to determine whether a is greater than b. If so, then we can subtract 2 repeatedly and also subtract 1 if the difference is odd; then the remaining number of steps is half the difference, rounded up. On the other hand, if a<b then we need to multiply by c until a≥b.

That gives us the core as

using Value = std::uint_fast32_t;

// untested!
Value minimumSteps(Value a, Value b, Value c)
{
    Value count = 0;
    if (a < b && (c <= 1 || !a)) {
        error(); // no finite solution
    }
    while (a < b) {
        ++count;
        a *= c;
    }
    return count + (a - b + 1) / 2;
}
\$\endgroup\$
5
  • \$\begingroup\$ Do you even need the remaining while-loop? \$\endgroup\$ Commented Apr 26, 2023 at 8:25
  • 1
    \$\begingroup\$ @G.Sliepen, I think so, if we want to keep it to integer arithmetic. I was reluctant to use std::log() due to the usual floating-point precision issues. \$\endgroup\$ Commented Apr 26, 2023 at 8:40
  • \$\begingroup\$ Oh yes - thought about zero, but not one. Fixing that now. (I did say it was untested!) \$\endgroup\$ Commented Apr 26, 2023 at 11:59
  • 1
    \$\begingroup\$ Your algorithm is wrong. Consider 5 12 3. Your algorithm sais 3 (12=5*3-2-1). But minimum steps is 2 (12=(5-1)*3). \$\endgroup\$ Commented Apr 26, 2023 at 19:09
  • \$\begingroup\$ @slepic, you're right of course. I hope this answer at least provides some insight towards a more directed solution search (if we've multiplied one or more times by c, we have those extra divisors available). \$\endgroup\$ Commented Apr 27, 2023 at 6:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.