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. If the first number of a digital river is k we will call it river k.
For example, river 480 is the sequence beginning {480, 492, 507, 519, ...} and 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, 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 which inputs a single integer n (1<=n<=16384), and
outputs the value where river n first meets one of these three
rivers.
Sample run
River: 86
First meets river 1 at 101 - What is the
lowest number that can be found in exactly 100 digital
rivers?
[For example, 8 is the lowest number in 4 rivers: rivers 1, 2, 4, and 8.] - Every digital river will eventually meet river 1, river 3
or river 9. Write a program which inputs a single integer
n (1 <= n <= 16384), and outputs the value where
river n first meets one of these three rivers.
Sample run
River 86
First meets river 1 at 101
Worked solution
Statement of question 1:
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. If the first number of a digital river is k we will call it river k. ... 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, meets river 507 at 507, and never meets river 481
Worked solution.
The first problem we must solve is to find the next number in the sequence. It is a good idea to write a function that does this as we will be calling it several times.
Given a starting point n, we begin with a variable s set to n, then add the sum of the digits of s to n. We do this by repeatedly dividing s by 10, adding the remainder to n each time, until s becomes zero. The remainder is calculated using the % operator in C++. Code to do this is given below.
int nextRiver( int n )
{
int s = n;
while( s > 0 )
{
n = n + (s % 10);
s = s / 10;
}
return n;
}
You can then call nextRiver(a) to find the next value in the sequence after a. It is straightforward to use this to follow a digital river.
The question is a little more complicated than that, however. We are told that if we follow rivers 1, 3 and 9 and any river far n enough, river n will meet one of the other three. (Proving this is not straightforward and is left to reader's curiosity.) This lets us note the following about the algorithm we will use to solve the problem.
We need to store four things: the current value in river n, and the current values in river 1, river 3 and river 9. Appropriate starting values for these are n, 1, 3 and 9.
Before every move we should check if river n has met one of the other three (for example, if we start with n=1 there is nothing to do).
The method I chose works as follows.
Repeatedly move downstream in rivers 1, 3 and 9 until we reach or pass n.
If we haven't reached a meeting point, move one step down river n.
Keep doing this until we reach a meeting point.
Code that achieves this is as follows. It is assumed that n is declared elsewhere and is already set to the starting value.
void parta()
{
/* river1, river3 and river9 will be used to hold the current value
in river 1, river 3 and river 9 as we follow them along. */
int river1 = 1;
int river3 = 3;
int river9 = 9;
/* If we have not found a match, move along rivers 1, 3 and 9
until we meet or pass n. If we still haven't got a meeting,
move one step along river n. */
while( (n != river1) && (n != river3) && (n != river9) )
{
while( river1 < n ) river1 = nextRiver( river1 );
while( river3 < n ) river3 = nextRiver( river3 );
while( river9 < n ) river9 = nextRiver( river9 );
if( (n != river1) && (n != river3) && (n != river9) )
n = nextRiver(n);
}
/* Show the solution */<
if( river1 == n )
cout << "First meets river 1 at " << n;
if( river3 == n )
cout << "First meets river 3 at " << n;
if( river9 == n )
cout << "First meets river 9 at " << n;
}
All that is then required is to set up the program to read in n and call parta.
Marking (a).
For each test of the program for 1(a) you need to type in a single integer. The response should be a statement containing two integers; there is [1] point available for each correct integer. There are no points for incorrect answers.
[2] 86 1 101 [2] 108 9 117 [2] 165 3 204 [2] 852 3 1020 [2] 999 9 999 [2] 4759 1 10003 [2] 13046 1 20014
Additional marks are
available for general program behavior.
[2] Program inputs
numbers.
[2] For each test a statement containing two numbers is
output.
[2] Program terminates without crashing/hanging.
A total of [20] points available for a correct solution to (a).
(b). What is the lowest number that can be found in exactly 100 digital rivers? [For example, 8 is the lowest number in 4 rivers: rivers 1, 2, 4, and 8.]
The hardest part about this question is understanding what is meant by a number being 'in' several different rivers. In this example, 4 rivers include the value 8: river 8, river 4 (with the values 4, 8, ...), river 2 (going 2, 4, 8, ...) and river 1 (1, 2, 4, 8, ...). Each of these is considered to be a different river. In this case, they all happen to follow from river 1, but that will not be the case in general because rivers merge.
The way to solve this is to count the times each number is met as we follow every river in turn. We start with an array hits[], initially set to zeros. We follow river 1, incrementing the appropriate element of hits[] for each point in river 1, stopping at some end value. We then follow river 2, then river 3, and so on, in the same way, stopping when we've followed all the rivers up to our chosen terminating value. We can then check to find which number is the lowest that it an element in exactly 100 different rivers.
I chose 500 as the end point, which just happened to be large enough. If you'd started with a value smaller than the correct answer, 416, the program would not have found a solution and you would have known to try a bigger end value.
This can be achieved using the following code, which calls nextRiver().
void partb()
{
int start; /* Current starting river */
int current; /* Position in river start */
int hits [500]; /* Number of times we've met each value */
/* Initialise number of hits to zero */
for( current = 1; current < 500; current++ )
hits[current] = 0;
/* Follow rivers 1 to 500 */
for( start = 1; start < 500; start++ )
{
current = start;
while( current < 500 )
{
hits[current]++;
current = nextRiver( current );
}
}
/* Find the first time we meet a number 100 times */
for( current = 1; current < 500; current++ )
if( hits[current] == 100 )
{
cout << "First number in 100 rivers is " << current;
break;
}
}