2015年8月19日星期三

Lint code: Binary Representation

Given a (decimal - e.g. 3.72) number that is passed in as a string, return the binary representation that is passed in as a string. If the fractional part of the number can not be represented accurately in binary with at most 32 characters, return ERROR.
Have you met this question in a real interview? 
Yes
Example
For n = "3.72", return "ERROR".
For n = "3.5", return "11.1".
Tags Expand 

My solution:
First, extract the left part and right part into two int; O(n) -- n is the length of input string
Second, turn the left part to binary string by divide 2;
              O(logleft) -- less than O(32) -- left is the left part int
              turn the right part to binary string by multiply 2
              worst case O(32)
Finally, combine left and right string.

Worst case Time: O(n) + 2*O(32)
Worst case Space: O(64 chars) = O(1)

Many bugs apper:
1) When there real part is 0 or decimal part is 0
2) At first I use double to indicate the decimal part. But then it cannot figure out whether 0.5 * 2 == 1 after the initial value multiply two several times. Embarrased. In the end, I use int to indicate decimal
Here, note to use long type to indicate decimal values and limit.

Finally accepted, TAT


class Solution {
public:
    /**
     *@param n: Given a decimal number that is passed in as a string
     *@return: A string
     */
    string binaryRepresentation(string n) {
        // wirte your code here
        int left = 0;
        int i = 0;
        while(n[i] != '.'){
            left = left * 10 + n[i] -'0';
            i++;
        }
        string leftstr;
        while(left){
            leftstr = to_string(left % 2) + leftstr;
            left = left / 2;
        }
        
        long right = 0;
        int j = i + 1;
        while(j < n.size()){   
            right = right * 10 + n[j] - '0';
            j++;
        }
        long limit = pow(10, j - i -1);
        string rightstr;
 while(right){
  if(rightstr.size() > 32) return "ERROR";
  if(right * 2 >= limit){
   rightstr += '1';
   right = right * 2 - limit;
  }
  else {
   rightstr += '0';
   right *= 2;
  }
 }
        if(leftstr.empty()) leftstr = "0";
        if(rightstr.empty()) return leftstr;
        return leftstr + '.' + rightstr;
    }
};

没有评论:

发表评论