What should be the correct approach to solve the “Missing Number” problem?
LINK: CodeChef: Practical coding for everyone
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…CodeChef: Practical coding for everyone …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
@hellbrazer Bro you just need to store all the possibilities of a number in all the possible bases it can have…yes, it will be in time limit…and at last you just check if there is an elements which was present in all the arrays(1 array for each of the number in all his bases)…this way you can find if the number exist or not…
1 Like
You don’t have to start base from 2 but from the minimum possible base. Remember that for kth-base representation, maximum number that can show up is (k-1).
https://www.codechef.com/viewsolution/27219532
1 Like
@bugs_bunny_001 yeah you are right…but python comes with exceptions handling…you can use that to avoid exceptions…