c# O(log n) divide and conquere solution


  • 0
    R

    For some explanation please ask. Thanks.

    public class Solution {
        public int Divide(int dividend, int divisor)
            {
                if (divisor == 0)
                {
                    return int.MaxValue;
                }
                if (dividend == 0)
                {
                    return 0;
                }
    
                bool neg = false;
                if (Math.Sign(dividend) + Math.Sign(divisor) == 0)
                {
                    neg = true;
                }
    
                long dividendTemp = Math.Abs((long)dividend);
                long divisorTemp = Math.Abs((long)divisor);
    
                long rest;
                long result = RecursiveDiv(dividendTemp, divisorTemp, out rest);
    
                if (neg)
                {
                    result = -result;
                }
    
                if (result > int.MaxValue)
                {
                    return int.MaxValue;
                }
                return (int)result;
            }
    
            private long RecursiveDiv(long dividend, long divisor, out long rest)
            {
                if (dividend < divisor)
                {
                    rest = dividend;
                    return 0;
                }
                else
                {
                    long restTemp;
                    long result = RecursiveDiv(dividend >> 1, divisor, out restTemp);
                    result <<= 1;
                    restTemp <<= 1;
    
                    if ((dividend & 1) > 0)
                    {
                        restTemp++;
                    }
    
                    if (restTemp >= divisor)
                    {
                        result++;
                        restTemp -= divisor;
                    }
    
                    rest = restTemp;
    
                    return result;
                }
            }
    }
    

  • 0
    R

    Sorry it is not dive and conquere, it is not the right term, but it is O(log n) time complexity.


Log in to reply
 

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