# Division & Dynamic Programming

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 ofCode Storieswhere 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≤

1K≤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 yourN= 123Now you want to generate candidate solutions by removing:

-0 digits:123

-1 digits:23, 13, 12

-2 digits:1, 2, 3NOTE: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:

ConsiderN = 123andK = 2Now, stateS[0,1]depicts the case where you are on choosing thefirstdigit (index 0) and taking its remainder with2(which is 1). You can see its value will betrueas you can just include the second digit and the combined numberwill be divisible by122. Thereforce, S[0,1] will evaluate totrue.

## 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 stateS[i, j]as eithertrueorfalse.

## 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