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!
It could be written like this.
you can refer to my solution, I think it's much clearer 43701050
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.