uninterested._.coder's blog

Jio SDE OA Question
By uninterested._.coder, 2 years ago, In English

You have given a number n you have to return the smallest possible palindrome number of digit n which is divisble by 7.

1<=n<=1000

Input :

4 -> no of test cases

1

2

3

4

output :

0

77

161

1001

####

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

Comments Comments (11)
| Write comment?
»
2 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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,....,9pal9

Compute 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 mod

dp[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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 


    #include <iostream>
#include <vector>

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<int> 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;
}
    → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I code for you dear :) uninterested._.coder I got nothing to do. HEHE

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you nailed it brother question be like: are you here to distroy me

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      haha thanks, but I only notice a good observation to reduce code :) Anyways, it is O(n) given n of digits. So pretty good.

      → Reply
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

~~~~~

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    @bhikkhu how were you able to generate all these strings which are divisible by 7 manually ?

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want detailed help I can share more information to increase your understanding. :) Happy to help.

→ Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes please help with this along with resources where this type of dp can be learned

    → Reply