Divide Two Integers, Fraction to Recurring Decimal

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

Solution Subtraction

• public static int divide2(int dividend, int divisor) { 
         if (dividend == 0 || divisor == 0) { 
             return 0; 
         } 
         long a = Math.abs((long) dividend); 
         long b = Math.abs((long) divisor); 
         if (b > a) { 
             return 0; 
         } 
    
         long sum = 0; 
         long pow = 0; 
         long result = 0; 
         while (a >= b) { 
             pow = 1; 
             sum = b; 
             while (sum + sum <= a) { 
                 sum += sum; 
                 pow += pow; 
             } 
             a -= sum; 
             result += pow; 
         }
         result = ((((dividend ^ divisor) >> 31) & 1) == 1) ? -result: result;   
         
          if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
         	 
             return Integer.MAX_VALUE;
          }
           
          return (int)result;
     }

Solution Bit Manipulation

public static int divide(int dividend, int divisor){
  	  if (dividend == 0 || divisor == 0) { 
            return 0; 
        } 
        long a = Math.abs((long) dividend); 
        long b = Math.abs((long) divisor); 
        long bb = Math.abs((long) divisor); 
        if (b > a) { 
            return 0; 
        } 
        long sum = 0; 
        long pow = 0; 
        long count = 1;
        long result=0;
        while(a>bb){
      	  bb=bb<<1;
      	  count=count<<1;
        }
       
        while (a>=b){
            while (a>=bb){
                a -= bb;
                result = result+count;
            }
            bb=bb>>1;
      	  count=count>>1;    
        }
        
        result = ((((dividend ^ divisor) >> 31) & 1) == 1) ? -result: result;
        
        if (result > Integer.MAX_VALUE || result < Integer.MIN_VALUE) {
       	 
           return Integer.MAX_VALUE;
        }
        
        return (int)result;       
  }

---

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
For example,
Given numerator = 1, denominator = 2, return “0.5”.
Given numerator = 2, denominator = 1, return “2”.
Given numerator = 2, denominator = 3, return “0.(6)”.

Solution

+The key insight here is to notice that once the remainder starts repeating, so does the divided result.

+You will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.

+The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.

+Just like the question Divide Two Integers, be wary of edge case such as negative fractions and nasty extreme case such as -2147483648 / -1.

public String fractionToDecimal(int num, int den) {
        StringBuilder sb = new StringBuilder();
        if(num == 0 || den==0) return "0";
        //sign
        sb.append(((num > 0) ^ (den > 0)) ? "-" : "");
        //integer
        long numerator = Math.abs((long)num);
        long denominator = Math.abs((long)den);
        sb.append(numerator/denominator);
        long residual=numerator%denominator;
        if(residual==0) return sb.toString();
        //factorial
        sb.append(".");
        HashMap<Long, Integer> map=new HashMap<Long, Integer>();
        map.put(residual, sb.length());
        while(residual!=0){
            sb.append(residual*10 / denominator);
            residual=(residual*10) % denominator;
            if(map.containsKey(residual)){
                sb.insert(map.get(residual), "(");
                sb.append(")");
                break;
            }
            else{
                map.put(residual, sb.length());
            }
        }
        return sb.toString();  
    }