Merging Digital River 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&lt;iostream&gt;
using namespace std;
int sum_of_digits(int);
int connect(int start_number, int chk_number)
{
    while (true)
    {
        if (start_number&gt;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&gt;0)
    {
        sum_of_digit += number % 10;
        number /= 10;
    }
    return sum_of_digit;
}

int main()
{
    int x, temp;
    int m = 1;
    while (x != 0)
    {
        cin &gt;&gt; x;
        temp = x;
        bool flag = false;
        while (true)
        {
            for (int i = 1; i &lt; 10;)
            {
                if (connect(i, temp) != -1)
                {
                    cout &lt;&lt; "Case #" &lt;&lt; m &lt;&lt; endl;
                    cout &lt;&lt; "first meets river of " &lt;&lt; i &lt;&lt; " at " &lt;&lt; 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.
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.