C# solution: DFS with explanation


  • 0
    B

    For example:

    We want to get: 100 / 4 = ?
    The easiest way is to 100 - 4 - 4 - 4 ..... - 4 until it is 0, but it is too slow.

    There are two ways to reduce the time, shrink the range of dividend or expand the range of divisor.

    if we shrink the range of dividend, we do not know whether the remainder is 0 or not, such as 3 / 2 = 1 remainder: 1.

    So the only way is to expand the range of divisor because multiple does not lose the precision.

    So we do like this:
    100 / (4 * 2 * 2 * 2 * 2) = 100 / 64 = 1

    So we know if 4 expands 2 * 2 * 2 * 2, we can get 1, so we have to expand 1 for the final result.
    1 * 2 * 2 * 2 * 2 (1<<4) (because: ?*2 = ?<<1)

    Then we have 100 - 64 = 36 which needs to calculate:
    36 / (4 * 2 * 2 * 2) = 36 / 32 = 1 (1<<3)

    36 - 32 = 4
    4 / 4 == 1

    4 - 4 == 0 <---- we calculate all dividend.

    So the final result is 1 * 2 * 2 * 2 * 2 + 1 * 2 * 2 * 2 + 1 = 25

    public class Solution 
    {
        enum Sign { Positive, Negative }
    
        private Sign sign;
        public int Divide(int dividend, int divisor) 
        {
            if (divisor == 0) return  int.MaxValue;
            if (divisor == -1 && dividend == int.MinValue) return int.MaxValue;
    
            var sign = Sign.Positive;
    
            if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
            {
                sign = Sign.Negative;
            }
    
            var result = Divide(Math.Abs((long)dividend), Math.Abs((long)divisor));
    
            if (sign == Sign.Negative)
            {
                return -result;
            }
    
            return result;
        }
    
        private int Divide(long dividend, long divisor) 
        {
            if (dividend <  divisor) return 0;
            if (dividend == divisor) return 1;
    
            var multiples = 0;
    
            var tempDivisor = divisor;
            while(tempDivisor <= dividend)
            {
                multiples++;
                tempDivisor <<= 1;
            }
    
            // tempDividened > divisor
            multiples--;
            tempDivisor >>= 1;
    
            var nextDividend = dividend - tempDivisor;
    
            return Divide(nextDividend, divisor) | (1 << multiples);
        }
    
    
    }
    

Log in to reply
 

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