3
\$\begingroup\$

I am solving this question:

It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers. A digital river is a sequence of numbers where the number following n is n plus the sum of its digits.

FOR EXAMPLE

12345 is followed by 12360 since 1+2+3+4+5=15 and so 12345 + 15 gives 12360. similarly 145 is followed by 155. If the unit's digit of a digital river is 'M' we will call it river 'M'. For example, 231 would be called river 1.

river 480 is the sequence beginning {480,492,507,519....} river 483 is the sequence beginning {483,498,519,....}. normal streams and rivers can meet, and the same is true for digital rivers. This happens when two digital rivers share some of the same values.

FOR EXAMPLE:

River 480 meets river 483 at 519. river 480 meets river 507 at 507 and never meets river 481. Every digital river will eventually meet river 1, river 3 or river 9.

Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.

Input

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer \$n\$ (\$1 \le n \le 16384\$). A test case with value of 0 for n terminates the input and this test case must not be processed.

Output

For each test case in the input first output the test case number (starting from 1) as shown in the sample output. Then on a separate line output the line "first meets river x at y". Here y is the lowest value where river n first meets river x (x = 1 or 3 or 9).If river n meets river x at y for more than one value of x, output the lowest value. Print a blank line between two consecutive test cases.

Input:

86

12345

0

Output:

Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423

Here is the code to solve it:

#include<iostream>
using namespace std;
int sum_of_digits(int);
int connect(int start_number, int chk_number)
{
    while (true)
    {
        if (start_number>chk_number) break;
        else if (start_number == chk_number) return chk_number;
        else start_number += sum_of_digits(start_number);
    }
    return -1;
}
int sum_of_digits(int number)
{
    int sum_of_digit = 0;
    while (number>0)
    {
        sum_of_digit += number % 10;
        number /= 10;
    }
    return sum_of_digit;
}

int main()
{
    int x, temp;
    int m = 1;
    while (x != 0)
    {
        cin >> x;
        temp = x;
        bool flag = false;
        while (true)
        {
            for (int i = 1; i < 10;)
            {
                if (connect(i, temp) != -1)
                {
                    cout << "Case #" << m << endl;
                    cout << "first meets river of " << i << " at " << temp;
                    flag = true;
                    break;
                }
                if (i == 1) i = 3;
                else if (i == 3) i = 9;
                else break;
            }
            if (flag) break;
            temp += sum_of_digits(temp);

        }
    }
    return 0;
}

And I'm stuck because it takes more than 1 sec on some inputs. Please help me optimize it to below 1 second on any inputs.

Don't tell anything on using namespace std; and look at it as C code not C++ code. As it was in a competition I was in a hurry. It worked in the competition but now I want to make it fast.

\$\endgroup\$
2
  • \$\begingroup\$ I have rolled back the last edit. Please see What to do when someone answers. \$\endgroup\$
    – h.j.k.
    May 23 '15 at 13:48
  • \$\begingroup\$ @h.j.k. thanks for pointing out it to me. Sorry for my mistake \$\endgroup\$ May 23 '15 at 14:46
4
\$\begingroup\$

Your code is disappointing.... as C++. Really, it is a C program written in C++. There's no classes, objects, instances, etc. In part, this is one of the reasons your code is slow.

A natural consequence of the way you compute your answers is that you have to re-build the entire stream 1, 3, and 9 sequences each time the code encounters a new test. If you had a "stream" class for each of the three base classes, and you "remembered" the stream, and made it searchable, then you would have a way to look up whether a test stream value joins. Using an iterator would make sense for the process too.

Iterate the stream, find if there is an intersection, move on.

your code is actually far worse than I realized when it comes to calculating the base 1,3, and 9 streams.... it rebuilds each stream each time you test a new value, for each new value in each test case... thus, for example, you could be computing millions, and millions of values unnecessarily.

You need to "remember" and "index" the base streams, and you'll fare much better.

Also, use the language to your advantage: classes, iterators, vectors, etc.

\$\endgroup\$
4
  • \$\begingroup\$ yeah i agree with you. As I haven't learned STL \$\endgroup\$ May 22 '15 at 15:55
  • \$\begingroup\$ so don't know much about iterators,vectors \$\endgroup\$ May 22 '15 at 15:57
  • \$\begingroup\$ Then you should considering learning about C++ at its fullest, otherwise write these challenges in C instead. Even if you were in a hurry, it won't stop others from making such criticisms. \$\endgroup\$
    – Jamal
    May 22 '15 at 17:39
  • \$\begingroup\$ @Jamal yeah, if i replace it with scanf and printf it will be an c code. But i like to write in cin and cout as they are pretty neat appearing and i am able to type those faster than scanf and printf \$\endgroup\$ May 22 '15 at 17:49
3
\$\begingroup\$

This is not a critique about the speed, but about how you abuse loops.

    while (true)
    {
        for (int i = 1; i < 10;)
        {
            if (connect(i, temp) != -1)
            {
                cout << "Case #" << m << endl;
                cout << "first meets river of " << i << " at " << temp;
                flag = true;
                break;
            }
            if (i == 1) i = 3;
            else if (i == 3) i = 9;
            else break;
        }
        if (flag) break;
        temp += sum_of_digits(temp);

    }

while(true) is not a good idiom to use. It (or the preferred idiom for(;;) ) indicates that the loop is supposed to go on forever. Since that is no your intent, that's not the idiom you should use.

You want the loop body to execute at least once, so you should be using do { ... } while (...).

Secondly, the inner for "loop" really isn't a loop at all, is it? In reality you should just have 1, 3, and 9 in an array, and then loop over that array.

Thirdly, the "find the matching loop" should be a function all on its own, so that you can return immediately upon finding it, rather than setting flags and trying to break out of multiple loops.

\$\endgroup\$
1
  • \$\begingroup\$ thanks for inputs. I will use those techniques you mentioned \$\endgroup\$ May 24 '15 at 3:00
1
\$\begingroup\$

How did your program work at the competition?

int main()
{
    int x, temp;
    int m = 1;
    while (x != 0)
    {
        cin >> x;
        temp = x;
        ....

You declare x without initializing it and instead prompt for input in your loop, therefore, it is default initialized to 0. Next you hit the while loop and the condition evaluates as false and the program ends.

\$\endgroup\$
5
  • \$\begingroup\$ i don't think garbage values are equal to zeros. they are usually very greater value. And thanks for pointing it out. My bad. \$\endgroup\$ May 23 '15 at 2:29
  • 1
    \$\begingroup\$ @KishanKumar I think it depends on the compiler. Just to be safe you could get the x value input in the while loop as such: while(cin >> x && x != 0), since the && operand guarantees that the left expression is evaluated first. \$\endgroup\$
    – Ishaan
    May 23 '15 at 4:42
  • \$\begingroup\$ Only static variables are zero-initialized by default. The other variables are garbage-initialized. \$\endgroup\$
    – Morwenn
    May 23 '15 at 17:02
  • \$\begingroup\$ DevC++ initializes 'x' to 0 for me \$\endgroup\$
    – Ishaan
    May 23 '15 at 18:54
  • \$\begingroup\$ @ishyfishy Visual doesn't do it for me \$\endgroup\$ Jun 24 '15 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.