Division & Dynamic Programming

You can only connect the dots by looking backward

Problems can’t be considered easier or difficult in isolation.
It is essential to define the scale at which they need to be solved.
Today we will deal with an interesting problem that will reiterate this point.

Welcome! To the brand new article of Code Stories where each week we solve interesting problems using the fundamentals of Computer Science. 🚀

We will begin by understanding the problem statement in detail.
After that, we will focus on various solution approaches.
Finally, we will code the solution. 🎉

This article assumes that you have a basic understanding of Dynamic Programing. If you are new to the idea, please refer to this tutorial.

The Problem ❓

You are given a non-negative integer N, it has at most 1000 digits without any leading zeroes. Along with an integer K which is an integer between 1 to 100.

You have to determine if it is possible to remove some of the digits (possibly 0) so that the result contains at least 1 digit, forms a non-negative integer, doesn’t have leading zeroes & is divisible by K.

Please note, you can’t rearrange the digits which are left, after removals.
If a solution exists, you should print it. (Print any, if multiple).

The Strategy 💡

After reading the problem statement, we can quickly summarise the input constraints. This step is crucial for selecting the type of strategy we can employ.

Constraints:
1 ≤ lenght(N) ≤ 1000
1 ≤ K ≤ 100

Okay, let’s approach this problem in a simple way. We need to remove some digits from a ridiculously long number so that it is divisible by a number K.

There are 2 challenges in front of us:

Operating a 1000 digit number as an integer

Let’s consider that our language doesn’t have the support to operate upon such a large integer. In that case, we need to write our custom divisibility checker module to find out the divisibility of potential candidates.

You may argue, that you can do it or use a language that has a BIG INT support. Fair, enough! Let’s look at the other caveat.

Generating all possible candidate solutions

We are allowed to remove a certain number of digits from the number so that it can be divisible by K.

Since K can be anything, you need to generate all the candidate solutions and compare each of them against K for divisibility.

But, here is the catch. The idea of generating all the candidates is equivalent to generating subsets of a given set.

Say your N = 123
Now you want to generate candidate solutions by removing:
- 0 digits: 123 
- 1 digits: 23, 13, 12
- 2 digits: 1, 2, 3
NOTE: We can't remove all the 3 digits as per the questions

Just like above, where we have 2³-1 = 7 candidate solutions, there can be (2^lenght(N))-1 subsets for any N.

In the worst case, your subset generation module will timeout purely because 2¹⁰⁰⁰ is pretty large!

How large? Typically, you can perform 10⁶ operations (10⁶ ~ 2²⁰) in 1 second.

2²⁰ = 1 Second
2⁸⁰ = 37 Billion Years! (Universe is only 13.77 Billion Years Old)

So we can’t continue with the approach. We definitely need to look beyond the obvious now.

Since we can’t ascertain a general rule for the divisibility with K, we ought to surely search the entire subspace.
We do so while dividing the problems into overlapping subproblems and solving each of them only once.

Let’s try to think in terms of Dynamic Programming.

Defining states

Let’s define a State S[i, j] such that i is 0≤ i ≤ len(N) and j is 0 ≤ j < K.
Also, let Arr[len(N)] be an array of digits of integer N.

Here S[i, j] will be true only if we can add some digits from the array segment Arr[i, len(N)-1] to make it divisible by K.

The second state parameter, j stores the remainder against K for the number till now. Clearly, if we can have this remainder as 0 that will give us a number which is divisible by K. That will be our answer. For instance:

Consider N = 123 and K = 2
Now, state S[0,1] depicts the case where you are on choosing the first digit (index 0) and taking its remainder with 2 (which is 1). You can see its value will be true as you can just include the second digit and the combined number 12 will be divisible by 2. 
Thereforce, S[0,1] will evaluate to true.

Defining transitions

The next step in a Dynamic Programing technique is to define transitions between the states. Since you are breaking down your bigger problem into smaller constituent problems, you need a way to relate them.

Formally a transition is: S[i, j] →S[i`, j`]

Consider an arbitrary state S[i, j] from Arr[len(N)].

Now you can either choose to delete the current digit Arr[i] or not. So at each index of the array, you have exactly 2 choices.

If you are not deleting the current digit then you need to change the parameter j to take into consideration this digit, while computing the remainder of the number formed till now.

j` = ((j * 10) + Arr[i]) % K
i` = i + 1 

Contrarily, if you are deleting the current digit then, you need not perform any such transition to parameter j and can just move to the next index.

j` = j
i` = i + 1

So we can recurse down to both these states and check from what transition are we getting true (if at all) as a return value.
Depending upon that we can assign the value for the current state S[i, j] as either true or false.

Getting the number

Now we need to get the number that was divisible by K.

For that, as we are progressing towards the end of the digits, the moment we get a remainder as 0, we return true for all the preceding parent recursive calls that led us to this state. Based on this, we can simply store the digits whose inclusion led us to this true state.

Since we are describing a recursive solution here, that simply means pushing the current digit to a stack whenever we receive a true return value for a choice where we have retained the current digit. This will be clearer when we will see the code.

The Code 🎉

Input

356652
8

Output

3552

Code in C++14

Voila! 🌠

Want more content like this?

You can connect with me on Twitter here: abshekha