Divisibility by Eight

[froghramar]

Problem Links : hust Codeforces

This problem can be solved with at least two different approaches.

The first one is based on the "school" property of the divisibility by eight — number can be divided by eight if and only if its last three digits form a number that can be divided by eight. Thus, it is enough to test only numbers that can be obtained from the original one by crossing out and that contain at most three digits (so we check only all one-digit, two-digit and three-digit numbers). This can be done in O(len^3) with three nested loops (here len is the length of the original number).

The last and recommended approach uses dynamic programming. Let’s consider dp[I][J] is true if we can make a number deleting 0 or more digits till I with mod J ( mod by 8 )  and get a number divisible by 8 adding 0 or more digits from index I till last element. Now we have two options.
1. We can ignore the current digit and move to next digit. The mod remains unchanged (dp[I + 1][J]).
2. We can take the current digit and move to next digit. The mod becomes (J * 10 + digit) % 8. This state can be represented by dp[I][ (J * 10 + digit) % 8]

Now, there is a problem. We can’t take an empty string. So, we will add another parameter K on dp to decide whether the taken string is empty or not. In the first path K remains unchanged and in the second path K is always 1 as we have taken the current digit.

dp[I][J][k] = dp[I + 1][J][K] or dp[I + 1][ (J * 10 + digit) % 8 ][1]

Code:


#include <bits/stdc++.h>

using namespace std;

int ar[105], len;
int dp[105][8][2];

int F(int pos, int rem, int taken) {
 if(pos == len) {
 if(rem == 0 && taken > 0) return 1;
 else return 0;
 }
 
 if(dp[pos][rem][taken] != -1) {
 return dp[pos][rem][taken];
 }
 
 int res = F(pos + 1, rem, taken);
 res = res | F(pos + 1, (rem * 10 + ar[pos]) % 8, 1);
 dp[pos][rem][taken] = res;
 return res;
}

int main() {
 char str[105];
 scanf("%s", str);
 len = strlen(str);
 for(int i = 0; i < len; i++) {
 ar[i] = str[i] - 48;
 }
 memset(dp, -1, sizeof(dp));
 int res = F(0, 0, 0);
 if(res > 0) puts("Yes");
 else puts("No");
 return 0;
}


How to save the string if a answer exists?
If you solve the problem recursively, you can easily form the string from your function calling and pass the string to the next state.

Code:


#include <bits/stdc++.h>

using namespace std;

int ar[105], len;
int dp[105][8][2];
string r;

int F(int pos, int rem, int taken, string s) {
 if(pos == len) {
 if(rem == 0 && taken > 0){
 r = s;
 return 1;
 }
 else return 0;
 }
 
 if(dp[pos][rem][taken] != -1) {
 return dp[pos][rem][taken];
 }
 
 int res = F(pos + 1, rem, taken, s);
 res = res | F(pos + 1, (rem * 10 + ar[pos]) % 8, 1, s + (char)(ar[pos] + '0'));
 dp[pos][rem][taken] = res;
 return res;
}

int main() {
 char str[105];
 scanf("%s", str);
 len = strlen(str);
 for(int i = 0; i < len; i++) {
 ar[i] = str[i] - 48;
 }
 memset(dp, -1, sizeof(dp));
 int res = F(0, 0, 0, "");
 if(res > 0){
 puts("Yes");
 cout << r << endl;
 }
 else puts("No");
 return 0;
}