Divisibility by 8 || Codeforces Editorial

This blog post is for users seeking to understand alternative approach of the given problem :

Problem - C - Codeforces

For those who have not attempted this question, feel free to develop an approach for it. I have another problem for u if u solved it by brute force.

Okay, let’s talk about it!! The given constraints of the problem is too low — one can easily devise a brute force solution. Anyway, how bad can the complexity be — O( ¹⁰⁰C ₃) which is of the order of O(10⁵)😜. But, if no of digits is of the order of 10⁵, what would be your approach?? Also, if someone asks the same question with divisibility by 7 with digits limit 10⁵ ??😮

Brute force solution:

Find if 1 digit, 2 digits or 3 digits exist which is divisible by 8. This can be done by writing for loops for 1,2,3 times consecutively. Bad approach😐

Well, now we need Dynamic Programming(DP) to solve these higher bound problems.. Ok, first step first what should be the state of the DP??

A little thinking might lead u to formulating dp state as dp[i][j] :

dp[i][j] is true if it is possible to remove some of the digits(or none) from the first i digits and then calculate the value of number formed by remaining digits modulo 8 and the value comes out to be j(0≤j<8).

If not possible, then dp[i][j] would be false.

So, what are the state transitions??

How does the state of first “i” elements depend on the state of first “i-1” elements?? This part requires a good deal of thinking. Now, let’s say u want to calculate dp[i][j] , u need to concentrate on the i ᵗʰ digit. There are 2 cases for this digit —

1. We may include it in our answer🤩 , OR
2. We may not😋

For the first case (1) :

For j := 0; j < 8:

dp[i][(j*10+a ᵢ)%8] = (dp[i-1][j] || dp[i][(j*10+a ᵢ)%8] );

Why?? See, if for a given i,j, if dp[i-1][j] is true, it means after including a ᵢ, the total(j*10+a ᵢ) modulo 8 would also be true. Why j*10?? Because we moved one digit forward(added one more digit), so the initial number would get multiplied by 10. Now, dp[i][(j*10+a ᵢ)%8] may also be already true in other cases. For example: for a ᵢ=3 and j values from 0 to 7, we have:

j …….(j*10+3)%8

0 3
1 5
2 7
3 1
4 3
5 5
6 7
7 1

We have 3, 5, 7, 1 repeated, and this is true for any value of aᵢ : the first four values are repeated again. So, if dp[i][(j*10+a ᵢ)%8] is true for j = 0, while iterating when j = 4, we encounter a state for which we have already calculated value. So, u can also choose to iterate j from 0 to 3 only.

Now comes the part where we choose to not include the a ᵢ digit. In this case,

dp[i][(j*10)%8] = (dp[i-1][j] || dp[i][(j*10)%8])

The explanation goes the same as before : with only ai not included. Finally, find if any of dp[i][0] for 1≤i≤n is True. If it is true, there u go we have got a number out of the initial digits which is divisible by 8. Else, no matter how many digits we remove we won’t a number divisible by 8.

This type of problems come under the category of digit DP. But this is the general approach.

Wait, we didn’t talk about the base case!! Well, dp[1][a ᵢ%8] = true, else dp[1][j] = false (for j != a ᵢ%8). This said, we obtain a linear complexity in terms of the number of digits — O(n*8) which is very optimum as compared to the original brute force solution.

If u find any mistake in the blog or want to suggest any edits/approaches, U are more than welcome!!😃

Cheers!! Happy problem Solving!!!!