icode_247's blog

By icode_247, history, 5 years ago, In English

So i am trying to solve this problem`` And this is the tutorial i am referring to.Also this is the code. And I am trying to do it by dynamic approach. But can anyone please explain me this part :


` if (dp[i - 1][j] > dp[i][(j * 10 + arr[i]) % 8])` ` dp[i][(j * 10 + arr[i]) % 8] = dp[i - 1][j];` `` ` // If we exclude the number from our combination` ` if (dp[i — 1][j] > dp[i][j])` ` dp[i][j] = dp[i — 1][j];`

what is j * 10 + arr[i]) % 8 doing here?. what is j here?. It will be great if you could explain in details?

Thank you!

  • Vote: I like it
  • -11
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It could be written like this.

Code

you can refer to my solution, I think it's much clearer 43701050

»
5 years ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

It's using the rule: (x+y) mod m = ((x mod m)+(y mod m)) mod m. For example, to get 456 divided by 8, the method is:

4 % 8 => (4 % 8)*10 => (4 % 8*10+5) % 8 => (((4 % 8)*10+5) % 8)*10 => ((((4 % 8)*10+5) % 8)*10+6) % 8.

Simplified, it looks like 4 % 8 => 4 => 4*10 => 40 => (40+5) % 8 => 45 % 8 => (45 % 8)*10 => (45 % 8)*10+6 => ((45 % 8)*10+6) % 8 => (5*10+6) % 8 => 56 % 8 => 0.

Notice in one part above that we're multiplying 45 % 8 by 10. This is equal to (45*10) % 8 if we modify it to be ((45 % 8)*10) % 8 because it's in the form of x*10 mod m = ((x % m) * 10) mod m. This statement => ((45 % 8)*10+6) % 8 is equal to 456 % 8 because it's like saying (450 % 8 + 6) % 8.

Here's some pictures:

In these pictures, j is the value of the numbers mod 8. For each digit, in the row of the digit, you mark the j value of digit % 8. Also, for each marked j in the row above, you multiply it by 10, add it to the current digit, and mod by 8. I didn't explain getting the mod of the sub-numbers of the number but the picture shows it. The way this problem clicked for me though was noticing the modular arithmetic behind it.