Hello guys. I have difficulty manipulating big number in c++. Recently, attending a contest at URI, i dont solved a problem of converting big bumber (10^1000000) for binary number. Do you have any tips to solve this problem ??
Hi @thalyson. If you read the question carefully you will see that the limit of the number is 10^1000 and not 10^1000000 as you have interpreted. This is because an O(N^2) algorithm will pass easily when n=1000 while n=1000000 will give time limit exceeded.
The solution for n=1000 will be similar to the normal decimal to binary conversion you perform by hand. Firstly store the number in a string A. Now divide this number of 2 and get the quotient and store it in another string B. If the remainder obtained on division by 2 is 1 the add 1 to your answer. This can directly be found from the last digit. Now you continue with B as the new dividend and store the quotient in A.You can store it in a separate array but this will be space efficient. The only tricky part here is writing a decent method to divide the large number by 2. This should also be fairly straight forward. Just mimic normal division by hand for this
3 Likes
thanks so much for explain, i’am nb, but for now 