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
thanks so much for explain, i’am nb, but for now