 # MSNG (Correct Approach?)

What should be the correct approach to solve the “Missing Number” problem?

It’s trivial if some base is known.
If no base is known then, for each of the n numbers, compute minbase = max(digits in numbers[i]) + 1.
Then for each base in range [minbase,36] compute value of this number in decimal form.
Now you have possible values for the each of the n numbers can take individually. Find intersection of these sets and return minimum. At the heart, its brute force.

3 Likes

if any pythoner out here…https://www.codechef.com/viewsolution/27072114 …a good solution for you bro…if you are having any problem in understanding my solution…you can reply…

can anyone help me in debugging the solution
https://www.codechef.com/viewsolution/27374179

My approach: While taking input of n pairs, if base is not equal to “-1” then simply get its base in decimal and add it to set, if base == -1 then try all base from 2 to 36 and add it to temporary set, there is a set outside loop(‘ans’) if empty simply copy element from temporary to this set else do set intersection, and flag variable if at an intersection we see there are no common element set flag to false.

@rohitrks bro can you check my solution , where it went wrong . I have tested a lot of test cases but not getting any wrong answer.

I did the exact same thing and my second test case failed https://www.codechef.com/viewsolution/27367501

i exactly did the same but get TLS.

bhai , i want to know the logic you used. plz

calculations in toDeci will result in overflow

it long long int, still overflow?

What is the correct output if there is a single pair with a known base but its value is greater than 1,000,000,000,000?

in your code if you use the following test case
1
1
14 1111111111111111111111
i am getting output as -2295709183123410629 instead of -1 which is due to overflow,well to control the overflow you could use the boost library in c++ which can handle very large numbers and to your query long long int can hold upto 18 digits but the decimal conversion could get more big

1 Like

I changed the code, now I think overflow is not happening there is some other problem
https://www.codechef.com/viewsolution/27376427

You should consider all the conditions that will cause overflow, e.g. `val = val * b`. I checked all the possibilities and finally got AC.

I guess the logic u are using is wrong…coz i ran your code for the test case
1
3
-1 100
-1 5A
-1 100
your code shows output as -1 instead of 100…unfortunately i am not able to find the problem in your code but if u want my insights/approach to solve the problem,i could write about the same

here is a link to my code
https://www.codechef.com/viewsolution/27361276
if u want any explanation,feel free to ask