1

Jio SDE OA Question

 1 year ago
source link: https://codeforces.com/blog/entry/109406?f0a28=1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By uninterested._.coder, 6 hours 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

output :

6 hours 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,....,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.

  • 5 hours ago, # ^ | 



    #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;
}

  • 5 hours ago, # ^ |

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

    • 4 hours ago, # ^ |

      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.

  • 4 hours ago, # ^ |

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

    • 3 hours ago, # ^ |

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

4 hours ago, # |

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

~~~~~

  • 4 hours ago, # ^ |

    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

4 hours ago, # |

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

  • 69 minutes ago, # ^ |

    thanks a lot man :)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK