Find the First Number k Divisible by Given Number n (Extended Approach)

• Download source code - 613 B

Contents

• Introduction
• Closer view
• How to solve
  • Time problem
  • Big size of input
  • Print output
    • By recursion
    • By stack
  • How to check -the mathematical solution-
  • The final code
• Complexity analysis
• Disadvantages

Introduction

You probably have solved the basic problem when you try to find the first number k that is divisible by a given number n, example:

input:
12
37
15

output:
2
37
5

And I can guess that you also solved this problem by sequential iteration from 1 until you find the number k that satisfies the only condition.

But suppose that there are more conditions in the problem statement like when I say: find the first number k that is divisible by n and the decimal representation of k consists of only zeroes and ones. And I can also say that the limit of input n is about 10^30 and the time limit is about 10 seconds, example:

input:
17
25
134
45618735

output:
11101
100
11010110
1011000100000110110110110

Closer View

When I put the previous constraints on the statement of the simple problem, it turned into a new problem with some tricky points...

First, you may notice that the "only zeroes and ones" constraint makes the problem bigger as if you choose to iterate until you find number k, you will need to check for every number x if its digit x[i] is zero, one or neither which makes the computations more complex.

The second constraint about the size of the input makes it impossible to solve this problem by normal iteration... as you see, the input size is a very large number and to find number k that satisfies these constraints, the output will reach the limit of about 10^100 , and for your knowledge, this number is much bigger than the number of atoms in the universe and it's impossible to fit such a large number in any memory made by mankind.

So, it's obvious that we need a new technique to solve this obstacle.

How to Solve

1. Time Problem

By iteration, you have to check all numbers between 1 and k if all its digits are zeroes and ones or not. It's a good waste of time. But, there's a better way.

Between 1 and 1000, there are only 8 numbers that satisfy the first condition and they are {1,10,11,100,101,110,111,1000}, so instead of iterating over 1000 numbers, we are interested only in 8 numbers, so we have to find a way to generate those numbers without caring about the rest of unwanted numbers. And for this solution, we can do the following...

Start with the number k=1
For each time, multiply k by 10 and add to it 0 for a time and 1 for another
Repeat step 2 until you find the wanted number
So, the implementation of this can be done by recursion as follows...

long long K=1; //The Initial Number We Will Start Searching With
long long wanted_number=10111010100; //The Number We Are Looking For
long long eps=1e15; //Big Number to Stop Recursion

bool find_binary_number(long long x=k){
    Cout<<x<<'\n'; //just to see the progress of generating
    if(x==wanted_number)
        return true;
    if(x>eps)
        return false;
    if(find_binary_number(x*10+0)) //(1)
        return true;
    if(find_binary_number(x*10+1)) //(2)
        return true;
}

The previous code will generate the following tree:

Notice

• The previous code is a prototype that shows the idea and will be changed in the final code.
• The variable eps is a big number defined as the limit of the generation and without it, the recursion will continue to generate a set of infinity numbers and cause an overflow.
• Statements 1 and 2 have if statements check for each call of the function if the final result of the call is true or not and we can't implement it without the if statement just like this...

find_binary_number(x*10+0);

as it will call the function and neglect its result and will stop if the function satisfies the stopping conditions without caring about the result if it's true or false.

And also can't implement it like that..

return find_binary_number(x*10+0);

because it will leave the function as soon as any branch of the recursion reaches the first return statement and won't continue the generation.

By this method, we have generated the only numbers we're interesting in and reduced the number of unneeded iterations that consume time.

2. Big Size of Input

As you know, the biggest data type in C++ is long double which has a size of 16 bytes and can store number with about 38 digits, still so far from our target size.

So you can use other languages like Python or Java which have other implementations that can store much bigger numbers.

But if you want to solve this problem in C/C++, you defiantly need to implement another data type to store what we want.

We can use the same idea of the array approach to store the separated digits of a number to store much bigger numbers and combine it with the previous technique.

We can do the following:

1. make a list to store each individual digits (only zeroes and ones)
2. generate a zero and a one and combine each digit with the index of the parent digit of the current digit in the list
3. insert the new element in the list
4. repeat steps 2 and 3 specific number of times

We can implement the previous technique like that...

struct state{ //struct represents an element
    int parent; 
    bool digit;
    state(int p, bool d){ //constructor
        parent=p;
        digit=d;
    }
};

vector<state> my_numbers; //list to store the digits

void generate_my_binary_numbers(int number_of_iteration=100){
    state initial_number(-1,1); //initial element
    my_numbers.push_back(initial_number);
    for(int i=0; i<number_of_iteration; ++i)
        for(int j=0; j<2; ++j){
            state new_state(i,j);
            my_numbers.push_back(new_state);
        }
}

Notice

• The previous code is a prototype that shows the idea and will be changed in the final code.
• This code generates digits mean nothing without combining some of them together to make a number, and it's not meant to generate a specific number, just a flow of binary digits and we will combine them later.
• The variable parent represents the index of the parent digit of the current digit in the list so it will be easy to track all the digits of any number.
• We inserted an initial element into the list with digit=1 and didn't insert 0 because zero on the left will mean nothing and parent=-1 to define that this is the first element and has no parent digit.

The previous code will generate a list like that...

current index:    0  1  2  3  4  5  6  7  8  9 10
digit        :    1  0  1  0  1  0  1  0  1  0  1
parent index :    -1 0  0  1  1  2  2  3  3  4  4

So if we want to generate a number from this list, all we want to do is to track the parent of every digit until we reach the root digit.

So, if we want to generate the number whose last digit is the digit in the index 10, we do the following:

1. Start with the inde x of the wanted digit
2. Check if this element is the last element
   • if yes: return from this function call
   • if no: call this function again with the parent index of the current element as a parameter
3. Print the current digit

3.Print Output

3.1. By Recursion

void get_parent_digit_by_recursion(int x){
    if(x==-1) //reached the last element
       return;
    get_parent_digit_by_recursion(my_numbers[x].parent);
    cout<<my_numbers[x].digit;
}

Notice

• We chose to use recursion in this function in order to print the digits in the right order as we stored it reversed
• This recursion may cause an overflow due to the big number of digits we have to print as the calling stack in C++ has a limited size
• We can solve the overflow problem by using our own stack and simulate the recursion process like that..

3.2. By Stack

void get_parent_digit_by_stack(int x){
    stack<bool>stk;
    while(x!=-1){
        stk.push(my_numbers[x].digit);
        x=my_numbers[x].parent;
    }
    while(stk.size()){
        cout<<stk.top();
        stk.pop();
    }
}

• We couldn't use a queue beacause -as we mentioned earlier- we want to print digits in the right order.
• We can also use a list instead of stack.

4.How to Check -The Mathematical Solution-

Now, we have solved all problems we mentioned earlier, but due to using this technique, we have another problem...

If we wanted to check if a number k is divisible by a number n, we can easily use...

if((k%n)==0)
    cout<<"It's divisible"<<endl;
else cout<<"It's not divisible";

but because we stored numbers as separated digits, we can't do that.

Maybe you think: why don't I combine the digits of every number I generate and check if it's divisible or not?!

This will be a disastrous technique because we used the previous technique to reduce the time and this method will do the opposite.

But fortunately, we can use the mathematical fact about modulo from number theory that says:

a mod n = (a mod n) mod n

and we can extend this fact to get:

<code> </code>b mod n = ((a mod n)*10^k+c) mod n

As modulo only cares about the reminder of the division, we can represent a number b in term of the modulo result of a number a.

55  mod 13 = 3
158 mod 13 = 2
158 mod 13 = (55 * 10^0 + 103) mod 13 = 2 
158 mod 13 = ((55 mod 13) * 10^0 + 103) mod 13 = 2 
As 158 = 55 * 10^0 + 103   &&   55 mod 13 = (55 mod 13) mod 13 
----------------------------------------------------
21  mod 14 = 7
211 mod 14 = 1
211 mod 14 = (21 * 10^1 +0) mod 14 = 1
211 mod 14 = ((21 mod 14) * 10^1 +0) mod 14 = 1
As 211 = 211 * 10^1 + 0    &&   21 mod 14 = (21 mod 14) mod 14

Notice:

• The term ((55 mod 13) mod 13) is equivalent to (55 mod 13) and the term (* 10^0 + 102) is only a way to transform 55 to 157, so we find that...

101  mod 23 = 9
1011 mod 23 = 22
1011 mod 23 = (101 * 10^1 + 1) mod 23 = 22
1011 mod 23 = ((101 mod 23) * 10^1 + 1) mod 23 = 22
As 1011 = 101 * 10^1 + 1   &&   1011 mod 23 = (1011 mod 23) mod 23

So, we now can easily solve this problem thus...

1. Add a new field mod to each element stores the modulo result of the number till now
2. Start with the initial element in the list with the variable digit=1 and store the value 1%n
3. Generate the next two digits (0,1) and use the mod value of the previous element to generate the new value
4. Repeat step 3 for all next elements

5.The Final Code

The implementation of the previous method will be:

struct state{ //struct represents an element
    int parent;
    bool digit;
    int mod;
    state(int p, bool d,int m){ //constructor
        parent=p;
        digit=d;
        mod=m;
    }
};

vector<state> my_numbers; //list to store the digits

//we chose the stack approach to avoid stack overflow
void get_parent_digit_by_stack(int x){
    stack<bool>stk;
    while(x!=-1){
        stk.push(my_numbers[x].digit);
        x=my_numbers[x].parent;
    }
    while(stk.size()){
        cout<<stk.top();
        stk.pop();
    }
}

void find_my_binary_numbers(int n){
    state initial_state(-1,1,1%n); //initial element
    my_numbers.push_back(initial_state);
    for(int i=0; ; ++i){
       state current_state=my_numbers[i];
       for(int j=0; j<2; ++j){
           state new_state(i,j,(current_state.mod*10+j)%n);
           my_numbers.push_back(new_state);
           if(new_state.mod==0){
               get_parent_digit_by_stack(my_numbers.size()-1);
               return;  
           }
       }
    }
}

The previous code will generate the following tree:

Notice

• The first loop has no stopping condition as we don't know when will the number k will appear
• We called function print_my_number with the last index in the list as a parameter because we know that the target element is the last element stored
• We sent the index of the target element to print_my_number function to track its previous digits and print them and neglected the rest of the digits.

Complexity Analysis

By the previous technique, we reduced time complexity in a great way.

Before Optimization

Assuming that we could solve our problem by regular iteration, the complexity would be....

Time Complexity

• big-O(k) for iteration
• For each iteration, you will check if its digits are binary or not... big-O(log(k))

After Optimization

Time complexity:

• As we iterate to generate only digits, the complexity will be big-O(log(k)) for iteration
• big-O(log(k)) for combining and printing the digits of the number

As k is a very large number upto 10^100, big-O(k) is a very very bad complexity, but big-O(log(k)) is only 100.

Disadvantages

By the previous method, we could solve our problem avoiding a lot of obstacles, but our solution has only one issue.

Because of generating two more digits in every iteration, the number of digits generated grows exponentially so for reaching a number k, we have to generate 2^[log(k)+1] elements.

To imagine how big is this, if the program reached numbers with 28 digits, it would generate 536870912 elements, and every element is not just an integer, it's a structure with three different data types of about 9 bytes, because of that, memory will be full immediately.