Solution for Divide Two Integers without Mod, Multiplication, Division


  • 0
    A
    • SOLUTION 1: There is a standard solution for this question which includes repeated subtraction. This is usually the normal solution.
    • SOLUTION 2: Then comes another solution in which we do right shift for division and left shift for multiplication and manipulate in term of bits. Example- We want to divide 187/7
           we keep Left Shifting 7 ie multiplying by 2, untill it is greater than 187. So
           14 (7<<2) (count=1)
           28 (14<<2) (count=2)
           56 (28<<2) (count=3)
           112 (56<<2) (count=4)------------*
           256 (112<<2) (count=5)
    Since 256 > 187, we take 112. Now at 112, count is 4. So we keep a tally variable. 
    tally = 2^count; (tally is 16 and reset count to 0)
    
    Again we repeat the same process with (187 - 112 = 75 as dividend) and 7 as divisor.
    Now again 7
                     14 (7<<2)(count=1)
                     28 (14<<2)(count=2)
                     56 (28<<2)(count=3)----------------*
                     112 (56<<2)(count=4)
    
    
    Since 112 > 75, we take 56. Here count is 3. So tally = tally + (2^ count);
    i.e. tally = 16 +8 = 24;
    
    Again repeat the process with (75-56 = 19 as dividend) and divisor =7;
    So 7
          14(7<<2)(count=1)---------------------*
          28(14<<2)(count=2)
    
    Since 28>19, we take 14. Here count=1. So tally = tally + (2^count);
    i.e. tally =16+8 + 2 =26;
    
    Now (19-14=5). Here 5 < 7. So we stop. This the final answer of 187/7 is 26 + 5/7. But talking in terms of int, we consider 26 only which is the answer.
    
    • SOLUTION 3: Then comes another solution, which is based on the log property of Log(a/b) = Log a - Log b. So we all to compute Loga - Logb. Then take the Antilog of the difference. Antilog is just raising the number by e(in this case as JavaScript uses Logx base e).
    var divide = function(dividend, divisor) {
        
    if(divisor ===1){
            return dividend;
        }
        
         var diffLog = Math.log(Math.abs(dividend)) - Math.log(Math.abs(divisor));
         var resultDiv = Math.pow(Math.E,diffLog);
        
        //If both are negative, simply return the result
        if(dividend < 0 && divisor < 0){
            return  resultDiv;        
        }
        
         //Then check if either one of them is a negative number
        // If so, then multiple the result with -1
        if(dividend < 0 || divisor < 0){
            return  resultDiv*(-1);
        }
    
        return resultDiv;
    };
    
    

    To cover edge cases, use if blocks like-

     if((Math.ceil(resultDiv) - resultDiv)< 0.0004)
            {
                return Math.ceil(resultDiv);
            }
        else{
            return Math.floor(resultDiv);
        
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.