Jio SDE OA Question - Codeforces

→ Обратите внимание

До соревнования
Good Bye 2024: 2025 is NEAR
41:05:01
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Jio SDE OA Question

Автор uninterested._.coder, 2 года назад, По-английски

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

uninterested._.coder
2 года назад
13

Комментарии (11)

Показать архивные | Написать комментарий?

bhikkhu

2 года назад, # |

← Rev. 4 →

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.

→ Ответить

bhikkhu

2 года назад, # ^ |



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

→ Ответить

bhikkhu

2 года назад, # ^ |

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

→ Ответить

bhikkhu

2 года назад, # ^ |

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.

→ Ответить

farmaan_khan

2 года назад, # ^ |

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

→ Ответить

bhikkhu

2 года назад, # ^ |

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

→ Ответить

bhikkhu

2 года назад, # |

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

~~~~~

→ Ответить

bhikkhu

2 года назад, # ^ |

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

→ Ответить