【第三轮】7.24-7.31 CareerCup 5.2

5.2 Given a real number between 0 and 7 (e.g., 0.72) that is passed in as a double, print the binary representation. If the number cannot be represented accurately in binary with at most 32 characters, print "ERROR."



回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改

I wonder that maybe the worst case of accurately representing a number in exactly 32 bits means:
the last digit (let's say X) of this number represented in decimalism must obey--->
assume the number has length N
0.0.....0X * 2^32 ==1
=>
X==(2^-32)*10^N;
from X is between 1~9 we can obtain N <= 9.633 , which means  N<10
Now we can assume all numbers represented in decimalism whose length is more than 11 will be a "ERROR" case, checking the length computation time is less than 12 (1 digit at a time) at the same time we do the transforming from decimalism to bits，less than 12.
Space to save the outcome of every multiplication and to save the final binary representation will be needed.
Time complexity is N(1)
Space complexity is N(1)

【解题思路】
Basic decimal representation, keep adding 2^-1,  2^-2... 2^-32 until the result equals to original decimal.

I'm having a hard time to understand what is "accurately" means...does it mean the result should strict equal to the original decimal, or could have some tiny rounding differences?

【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/fb3d73fc268b19b122d5

【解题思路】
check if x >0.5  if yes add 1 and x= x-0.5;   x = x*2 and check again;
【时间复杂度】
O(N)  N is the number of digits in Binary representation
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/jyhjuzi/7c30e0bd0a6b80e6bbef

between 0 and 1

【解题思路】
理解错题了，写了个输出IEEE754标准的，结果也懒得改了，基本思路都在里面，转化2进制，乘2或除2这两种思路都可以
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/Noahsark/8eaba401fdf37ef740c9

【解题思路】
keep substracting 0.5^n from the input value


【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/e3e05b8f3937ce114e49

【解题思路】
not even easy than the solution in the book.
multiply by 2 and check if 2n is greater than or equal to 1.


【时间复杂度】
O(1)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/UncleGarden/6c4e61c377da227fd4ff

【解题思路】
multiply by 2 and extract integer fraction
【时间复杂度】
O(1) - no more than 32
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/49aee9c2f58e46b4c38a

【解题思路】keep substracting 0.5^n from the input value,理解了好久才理解题目。果真智商让人捉急
【时间复杂度】o(n),不超过32位，是不是可以理解为n<32
【空间复杂度】o(1)
【gist link】https://gist.github.com/hilda8519/7aeb3efcbc60786edc6c