minimum number of moves required to convert a given into a lucky number

Question

You are given a number, at a time either you can increase a number by 1 or decrease by 1 it is considered as one move find the minimum number of moves required to convert a given into a lucky number. A number is called lucky if all the digits in it are even.

I have writtern the code but I am not sure if it is correct. Can anybody please confirm me?

#include<bits/stdc++.h>
using namespace std;

int count(int n)
{
    int count = 0;
    while (n != 0)
    {
        n = n / 10;
        ++count;
    }
    return count;
}

int firstDigit(int n)
{
    // Remove last digit from number
    // till only one digit is left
    while (n >= 10)
        n /= 10;
     
    // return the first digit
    return n;
}

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

    int i,j,ans=0;

    int x = count(n);

    while(x--)
    {
        if(firstDigit(n)%2 != 0)
        {
            if(firstDigit(n) == 9)
            {
                ans = ans + pow(10,x);
                n = n-pow(10,x);
            }

            else
            {
                ans = ans + pow(10,x);
                n = n + pow(10,x);
            }
        }
        
        else
        n = n - pow(10,x);

    }

    cout << ans << endl;

}

Edit:

I found it is giving wrong answer at 100. Can you please help me in finding out the mistake

good news: You can do it. Write tests. Work out expected output for some input with pen and paper and compare it to output of your code. Try to consider edge cases, for example input is already a lucky number, there are two possible solutions that are both optimal, etc. — 463035818_is_not_an_ai, Sep 02 '21 at 12:01
Compared to many other so-called "competition" or "online judge" submissions (which this looks like) you have pretty decent code. There are two things however, that you still need to change your habits: First and foremost [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h); Then [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Some programmer dude, Sep 02 '21 at 12:02
@463035818_is_not_a_number I tried, And till now it seems good — ububush, Sep 02 '21 at 12:04
Every time I see `pow(10,x)` it makes me sad. Floating point operation can be treacherous in such context. — Marek R, Sep 02 '21 at 12:07
@463035818_is_not_a_number I found it is giving wrong answer at 100. Can you please help me in finding mistake — ububush, Sep 02 '21 at 12:25
please do not change the question to ask for something else after you received answers. "How can I test it?" and "How can I fix it?" are two quite different questions — 463035818_is_not_an_ai, Sep 02 '21 at 12:28

463035818_is_not_an_ai · Answer 1 · 2021-09-02T12:16:32.460

1

Not all code can easily be tested, thats why you should strive to write testable code right from the start (instead of first writing it all and then try to confirm correctness). In your case testability could benefit a lot from moving most logic from main into a dedicated function:

 int minimal_steps(int input) {
        ....
 }

Once you have that, you can either call it in main with user supplied input just as you do it now, but you can also write tests more easily:

 void test() {
      assert( minimal_steps(2222) == 0);
      assert( minimal_steps(2221) == 1); 
      ...etc...
 }

Once you got into the habit of testing your code (you should also write tests for count and firstDigit) you may consider to use a testing framework to automate tests.

PS: It isnt wrong, but it is such a waste of CPU cycles that it is worth mentioning (actually it was already mentioned in a comment). You do not need to compute pow(10,x) in a loop where x is the loop counter. Consider that you are computing 10^2 almost as many times as the loop has iterations. Also 10^3 is the same in every iteration. Instead you should only update with *10 (in case x is incremented) or /10 when x decrements between iterations. Moreover, pow is for floating-points, not for integers.

edited Sep 02 '21 at 12:16

answered Sep 02 '21 at 12:08

463035818_is_not_an_ai

109,796
11
89
185

2

with catch2 live: https://godbolt.org/z/jcKPxedvb – Marek R Sep 02 '21 at 12:15
I found it is giving wrong answer at 100. Can you please help me in finding mistake – ububush Sep 02 '21 at 12:25
@ububush I already gave a hint in the answer: Test `count` and `firstDigit` to see if the mistake is there. Next step would be to use a debugger – 463035818_is_not_an_ai Sep 02 '21 at 12:30
@ububush I have no idea how your algorithm suppose to work, I see for example `if(firstDigit(n)%2 != 0)` and I have no clue why? So I have no idea how to fix it by not starting from scratch. I'm pretty sure others have similar problem. Maybe you should change your approach? Just iterate over all possible digits and calculate how many steps are needed to covert given number so it contains only that digit. Then just find minimum numbers of steps for that and you are done. This is simple brutal force approach with `O(n)` complexity so there is no point to search for something more smart. – Marek R Sep 02 '21 at 13:57

minimum number of moves required to convert a given into a lucky number

1 Answers1