Блог пользователя uninterested._.coder

Jio SDE OA Question
Автор uninterested._.coder, 20 месяцев назад, По-английски

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

####

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
20 месяцев назад, # |
← 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,....,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.

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится 


    #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;
}
    → Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится 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.

      → Ответить
»
20 месяцев назад, # |
  Проголосовать: нравится +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

~~~~~

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 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

    → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
20 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 часов назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить