### uninterested._.coder's blog

By uninterested._.coder, 21 month(s) ago,

#### 1001

####

• -6

| Write comment?
 » 21 month(s) ago, # | ← Rev. 4 →   0 You can solve it using dynamic programming.Each palindrome can have 7 states i.e. modulo 7.Lets denote the state by: [n][mod] is the smallest palindrome of digit n that has modulo 7 equal to mod.Then given the n digit palindrome = pal, (n+2) digit palindrome can be 0pal0,1pal1,....,9pal9Compute the dp[n][mod] = dp[n — 2][new_mod_with_digit_d] for every digit d, find first digit that gives true answer to minimize the palindrome.where new_mod_with_digit_d = (10^(n-1)*d + d + mod*10) % 7, since we add digit d at the front and back of the n-2 digit palindrome with mod moddp[n][mod] = boolean if such a palindrome exists, for simple storage, or even better if you store the last digit of the palindrome instead of boolean so that you can build back the palindrome easily by just traversing the states back.Very simple brute force.
•  » » 21 month(s) ago, # ^ |   0 #include #include using namespace std; //lets offset the digit by 1 for easiness char dp[1001][7]; char dp_non_zero[1001][7]; int nxt_mod[1001][7]; int non_zero_nxt_mod[1001][7]; int main() { vector queries = {1, 2, 3, 4}; for (int i = 0; i < 10; ++i) { if (dp[1][i % 7] == 0) { dp[1][i % 7] = '0' + i; } } int base_mod = 10 % 7; for (int i = 0; i <= 1000 - 2; ++i) { for (int j = 0; j < 7; ++j) { //current palindrome mod if ((i == 0 && j != 0) || (i > 0 && dp[i][j] == 0)) { continue; } for (int k = 0; k < 10; ++k) { // new digit int new_mod = (base_mod * k + k + j * 10) % 7; if (dp[i + 2][new_mod] == 0 || dp[i + 2][new_mod] > '0' + k) { dp[i + 2][new_mod] = '0' + k; nxt_mod[i + 2][new_mod] = j; } if (!k) continue; if (dp_non_zero[i + 2][new_mod] == 0 || dp_non_zero[i + 2][new_mod] > '0' + k) { dp_non_zero[i + 2][new_mod] = '0' + k; non_zero_nxt_mod[i + 2][new_mod] = j; } } } base_mod = (base_mod * 10) % 7; } for (int q: queries) { if (q == 1) { cout << 0 << endl; continue; } if (!dp_non_zero[q][0]) { cout << "No solution" << endl; continue; } string front(1, dp_non_zero[q][0]); string back(1, dp_non_zero[q][0]); int mod = non_zero_nxt_mod[q][0]; q -= 2; while (q) { front += dp[q][mod]; if (q > 1) back += dp[q][mod]; else break; mod = nxt_mod[q][mod]; q -= 2; } reverse(back.begin(),back.end()); cout << front + back << endl; } return 0; } 
•  » » 21 month(s) ago, # ^ |   +1 I code for you dear :) uninterested._.coder I got nothing to do. HEHE
•  » » » 21 month(s) ago, # ^ |   +1 Note: You can probably optimize the memory, I added non zero for ignoring 00000 strings since those are also palindromes but invalid ones for the answer.This is just a rough sketch take time to optimize the memory.
•  » » 21 month(s) ago, # ^ |   0 you nailed it brother question be like: are you here to distroy me
•  » » » 21 month(s) ago, # ^ |   0 haha thanks, but I only notice a good observation to reduce code :) Anyways, it is O(n) given n of digits. So pretty good.
 » 21 month(s) ago, # |   +1 Interesting pattern I noticed. The answers for n >= 4, are always use binary digits 0 and 1 except for the middle ones. So, there is a direct way to calculate the palindrome. ~~~~~ 0 77 161 1001 10101 101101 1002001 10011001 100010001 1000000001 10000600001 100006600001 1000005000001 10000066000001 100000060000001 1000000000000001 10000000100000001 100000001100000001 1000000002000000001 10000000011000000001 100000000010000000001 1000000000000000000001 10000000000600000000001 100000000006600000000001 1000000000005000000000001 10000000000066000000000001 100000000000060000000000001 1000000000000000000000000001 10000000000000100000000000001 100000000000001100000000000001 1000000000000002000000000000001 10000000000000011000000000000001 100000000000000010000000000000001 1000000000000000000000000000000001 10000000000000000600000000000000001 100000000000000006600000000000000001 1000000000000000005000000000000000001 10000000000000000066000000000000000001 100000000000000000060000000000000000001 1000000000000000000000000000000000000001 10000000000000000000100000000000000000001 100000000000000000001100000000000000000001 1000000000000000000002000000000000000000001 10000000000000000000011000000000000000000001 100000000000000000000010000000000000000000001 1000000000000000000000000000000000000000000001 10000000000000000000000600000000000000000000001 100000000000000000000006600000000000000000000001 1000000000000000000000005000000000000000000000001 10000000000000000000000066000000000000000000000001~~~~~
•  » » 21 month(s) ago, # ^ |   0 Ok, seems like I get a shorter Idea, lets create a binary string 1000[00]0001, if the current modulo is 0, this is the answer, otherwise, we can always increase the middle one by one digit while trying to get a palindrome i.e. middle one can be, 0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99
•  » » 7 months ago, # ^ |   0 @bhikkhu how were you able to generate all these strings which are divisible by 7 manually ?
 » 21 month(s) ago, # |   0 If you want detailed help I can share more information to increase your understanding. :) Happy to help.
•  » » 3 weeks ago, # ^ |   0 yes please help with this along with resources where this type of dp can be learned