Need explanation to the function isDigitIncreasing()

[CollinsLainzo]

Hi guys,

I succeeded in getting solution to a problem. The problem is:
A number is called digit-increasing if it is equal to n + nn + nnn + ... for some digit n between 1 and 9.
For example 24 is digit-increasing because it equals 2 + 22 (here n = 2)
For example 984 is digit-increasing because it equals 8 + 88 + 888
Write a function called isDigitIncreasing that returns 1 if its argument is digit-increasing otherwise, it returns 0.
The signature of the method is
int isDigitIncreasing(int n)

And a solution which works perfectly is:

#include <iostream>
using namespace std;
int isDigitIncreasing(int n);
int main()
{
	int num;
	cout<<"Enter number: ";
	cin>>num;
	cout<<isDigitIncreasing(num);
}
int isDigitIncreasing(int n)
{
	if(n<10)
	return 1;
	for(int i=1; i<=9; i++)
	{
		int tempsum=i;
		int previous=i;
		while(tempsum<=n)
		{
			previous = previous*10+i;
			tempsum=tempsum+previous;
			if(tempsum==n)
			{
				return 1;
			}
		}
	}
	return 0;
}

My problem is i'm struggling to understand and explain this function. I need someone who could help with an explanation (if possible add comment lines) that could help justify the general formula n+nn+nnn+... (where n is between 1 and 9) to the problem.

[Grime]

if(n<10)
return 1;

Says that every single-digit number qualifies as 'digit-increasing' (all single-digit numbers are < 10).

A 'digit-increasing' consists of addition of numbers with the same digit. That digit can be any digit so it could be
0 + 00 + 00 or
1 + 11 + 11 etc.
But 0 + 00 + 00 +.. = 0. And our if (n < 10) takes care of this.

So we only need to worry about the digits 1 through 9.
for(int i=1; i<=9; i++)

Let's consider a 'digit-increasing' number formed by the addition of digit 1.
1 + 11 + 111 +...
We can write 1 as: 1
We can write 11 as: 10x1 + 1
We can write 111 as: 10x10x1 + 10x1 + 1

See the pattern? That's essentially what we'll do, programmatically.

So for(int i=1; i<=9; i++) is for testing with all digits, not just 1.

int tempsum=i;
int previous=i;

tempsum will contain the sum (like with 10x1 + 1)
previous will contain the previous power of ten.

while(tempsum<=n) Makes sure we stop when the sum exceeds n.

if(tempsum==n)
{
	return 1;
}

^ If we've found that the sum == n then it's a 'increasing-digit'.

previous = previous*10+i;
tempsum=tempsum+previous;

This is the most important part of the code.

What that says is to follow the pattern i + 10*i + 10*10*i +...
See that it is similar to 1 + 11 + 111 +..

That's basically it.

[jonnin]

not seeing a way to avoid brute the force here. head exploding lol.
only improvement I have so far is a type of binary search on the digits. that is, try digit 5, if that is too big for the number of terms (which appears to be the number of digits in the input, in all cases, not 100% sure of that yet, but I think its true) then try 2 or 3, etc... no need to try 6-9 if 5 is too big ...

[lastchance]

#include <iostream>
#include <algorithm>
using namespace std;

bool isDigitIncreasing( unsigned long long n )
{
   const unsigned long long A[] = { 1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789 };
   for ( int i = 1; i <= 9; i++ )
       if ( !( n % i) && find( A, A + 9, n / i ) != A + 9 ) return true;
   return false;
}

int main()
{
   unsigned long long n;
   cout << "Input n (>0): ";   cin >> n;
   cout << boolalpha << isDigitIncreasing( n );
}

[ne555]

> not seeing a way to avoid brute the force here
n + nn + nnn + ... = value
may be decomposed as
n + (10 n + n) + (100 n + 10 n + n) + ,,, + (10^(x-1) n + 10^(x-2) n + ... + n) = value
regrouping
xn + 10 (x-1) n + 100 (x-2) n + ... + 100...0 n = value
and again
n [ x + 10 (x-1) + 100 (x-2) + ... + 100...0) = value
the second factor has the form 12345... where x is the number of digits of value, or one less.

now, you only care that that multiplication is possible with integer factors, so you may test value % n (n in [1:9])
or value % 12345... (two tries)

[jonnin]

the second factor has the form 12345... where x is the number of digits of value, or one less.

this is what I was not seeing. I got the equations but couldn't spot the pattern. Nice.