Digit-increasing number test

Question

A number is called digit-increasing if it is equal 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).

Actually, a friend of mine asked me this question and i am stuck thinking about it but couldn't find the exact solution so far. Can anyone help ? I needed the function that returns true if it is digit-increasing else false.

Answer 1

Here is another answer in Java that returns 1 if the number is digit-increasing, else it returns 0.

public class Program {
    static int power(int base, int exp) {
        int result = 1;
        for (; exp > 0; exp--) {
            result *= base;
        }
        return result;
    }
    
    static int nextNumber(int j, int digit) {
        int nextNum = 0;
        int k = 0;
        for (int i = j; i > 0; i /= 10, k++) {
            nextNum += digit * power(10, k);
        }
        nextNum += digit * power(10, k);
        
        return nextNum;
    }
    
    static int isDigitIncreasing(int n) {
        for (int i = 1; i <= 9; i++) {
            for (int j = i; j <= n;) {
                if (j == n) {
                    return 1;
                }
                j += nextNumber(j, i);
            }
        }
        
        return 0;
    }
    
    public static void main(String[] args) {
        System.out.println(isDigitIncreasing(24));
    }
}

Answer 2

// Example program
#include <iostream>
#include <string>


int isDigitIncreasingNo(int n) {

    if(n<=0)
      return 0;

    int len = std::to_string(n).length();

    int vector1 = 0;
    int vector2 = 0;

    for(int i=1;i<=len;i++)
       vector2 = (vector2*10)+i;

    vector1 = vector2/10;

    if(n % vector2 == 0 && (n / vector2)<=9  )
        return 1;

    if(n % vector1 == 0 && (n / vector1)<=9  )
        return 1;

    return 0;
}

int main()
{
  for (int i=0; i<10000000; i++) {
        if (isDigitIncreasingNo(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

Answer 3

General representation is:

n + (n*10 + n) + (n*100+n)...

If number look like sum of same digits then any digit can be represented as

(1+111+...) * base_digit

. Assuming this we can use simple algorithm:

bool isDigitIncreasing(const int num)
{
    int n = 1;
    int sum = 1; //value to increase n
    while (n <= num) {
        //if num is (111...) * base_digit and base_digit is < 10
        if (num % n == 0 && n * 10 > num) return true;
        sum = sum * 10 + 1; //N*10+N where n is 1 as was assumed
        n += sum;  //next step
    }
    return false;
}

Answer 4

Let d(k) be 1+11+111+...+(11...11) where the last number has k digits. Then d(1)=1, and d(k+1)=10d(k)+k+1.

We want to test if d(k)*i = n, for some k, and for some i=1..9.

If we've computed d(k), then i (if it exists) must be n/d(k). We can check if n/d(k) is correct, by comparing n with ((n/d(k))%10)*d(k). The %10 makes the test fail if i is larger than 9.

This gives us a relatively terse solution: compute subsequent d(k) until they are bigger than n, and at each point check to see if n is a digit-multiple of d(k).

Here's a very lightly code-golfed implementation of that idea:

#include <stdio.h>

int is_digit_increasing(int n) {
    for(int d=1,k=1;d<=n;d=d*10+ ++k)if(n==(n/d)%10*d)return 1;
    return 0;
}

int main(int argc, char**argv) {
    for (int i=0; i<10000; i++) {
        if (is_digit_increasing(i)) {
            printf("%d\n", i);
        }
    }
    return 0;
}

Answer 5

Here is the shortest solution

 public static 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;
        }

Answer 6

 public boolean isDigitIncreasing(int number)

 {
  int sum;
  int size=calculateNumberOfDigits(number);

  for(int i=1;i<=9;i++)
   {
      sum=0;
      int temp=size;
      while(temp>=1)
        {
            for(int j=temp;j<=1;j--)
             {
                sum=sum+i*(int)Math.pow(10,j-1);
             }
            temp--;
         }
      if(sum==number)
       {
          return true;//Its a digit increasing
        }
    }

     return false;
  }

 public int calculateNumberOfDigits(int number)
  {
     int size=0;
     do
       {
             number=number/10;
             size++;
        }while(size>0);

       return size;
  }

Answer 7

Here is a python code.The basic logic here is that a digit increasing number if divided by a specific number between 1-9 gives a digit increasing number made of only ones.All the digit increasing numbers of 1 follow a specific pattern ie 12345678...

import sys
for n in range(1,10):
    a=1
    if k%n!=0:
        a=0
    else:
        g=str(k/n)
        j=int(g[0])
        for i in range(1,len(g)):
            if int(g[i])==j+1:
                j=int(g[i])
            else:
                a=0
                break
    if a==1:
        print "Yes,it is a digit increasing number"
        sys.exit(0)
print "No,it is not a digit increasing number"

Answer 8

There are only relatively few numbers with this property: Within the range of unsigned long long (64 bits), there are only 172 digit-increasing numbers.

Therefore, in terms of a practical solution, it makes sense to pre-compute them all and put them in a hash. Here is Python code for that:

# Auxiliary function that generates
# one of the 'nnnn' elements
def digits(digit,times):
  result = 0
  for i in range(times):
    result += digit*(10**i)
  return result

# Pre-computing a hash of digit-increasing
# numbers:
IncDig = {}
for i in range(1,30):
  for j in range(1,10):
    number = reduce(lambda x,y:x+y,[digits(j,k) for k in range(1,i+1)])
    IncDig[number] = None

Then the actual checking function is just a look-up in the hash:

def IncDigCheck(number):
  return (number in IncDig)

This is virtually O(1), and the time and space taken for the pre-calculation is minimal, because there are only 9 distinct digits (zero doesn't count), hence only K*9 combinations of type n + nn + ... for a sum of length K.

Answer 9

I have done in this way. Check out once.

int sum = 0, count =0;
bool flag = false;

public bool isDigitIncreasing(int input_number)
{
int  n= get_number_of_digit(input_number); // Gets number of digits
int sum = 0;
    for(int i=0;i<n;i++)
    {
        sum = sum*10+1;
        count = count + sum;
    }

    for(int i=1; i<=9;i++)
    {
        if((input_number)==count*i)
        {
            flag = true;
            break;
        }
        else
        flag = false;
    }
    return flag;

}

    public int get_number_of_digit(int num)
    {

        int size = 0;
        do
        {
            num = num/10;
            size++;
        }while(num>0);
        return size;
    }

Answer 10

Here num is the number and n is the digit

#include<stdio.h>

int f(int num,int n)
{
 int d=n;
 while(num>0)
 {
        num-=n;
        n=d+n*10;
 }
 if(num==0)
        return 1;
 else
        return 0;
}

int main()
{
 int num;
 int n;
 int flag;
 printf("Enter the number :");
 scanf("%d",&num);
 printf("Enter the digit :");
 scanf("%d",&n);
 flag = f(num,n);
 if(flag == 1)
        printf("It's in n+nn+nnn+...\n");
 if(flag ==0)
        printf("It's not\n");
 return 0;
}

Answer 11

Simplest possible way is do the addition (bottom-up), I'll use simple for loop:

List<int> numbersSum = new List<int>{1,2,3,4,5,6,7,8,9};
List<int> lastNumber = new List<int>{1,2,3,4,5,6,7,8,9};
for(int i=0;i<= lg n + 1;i++)
{

   for(int j=0;j<9;j++)
   {
      if(list[j] < n)
      {
          var lastNumberJ = lastNumber[j]*10+j+1;
          list[j] += lastNumberJ; // add numbers to see will be same as n.
          if (list[j] == n)
            return j+1;
          lastNumber[j] = lastNumberJ;
      }
   }   
}

return -1;

The important part is you just need at most log n iteration and also you can return sooner if all numbers are bigger than given number, this is O(log n) algorithm.

Answer 12

Ambiguitiy: Are the values 1-9 repeating for themselves? (too lazy to google this myself)

If 1-9 are repeating then following should work. If not, and you want the code to work only on values > 10 then you can initialize mult with 10.

int i, mult = 1, result, flag;

for( i=1; i<9; i++ )
{
    flag = 0;

    while( result < TARGET )
    {
        result = result+(i*mult);
        mult   = mult*10;

        if( result == TARGET )
        {
            flag = 1;
            break;
        }
    }
    if( flag == 1 )
        break;
}

After execution, i must contain the values for which RESULT is a repeating number IF the flag is 1. If flag is zero after execution then the TARGET isn't a repeating number.

I wonder if its possible that a number could be repeating for multiple values, just curious.

Answer 13

Simple exhaustive search will work.

def is_digit_increasing_number(x):
    # n = 1, 1+11, 1+11+111, ...
    n = 1
    i = 1
    while n <= x:
        if x % n == 0 and n * 10 > x:
            return True
        i += 1
        n = n * 10 + i
    return False