Thursday, August 27, 2015

LeetCode OJ - Divide Two Integers

Problem:

Please find the problem here.

Solution:

This is more complicated than I thought.

At the heart of the algorithm is grade school division, but do it in binary.

The great thing about binary is that the quotient is either one or zero, so when you shift to the point where you can divide, that's what we will need.

The algorithm is not optimal in two sense.

  • It uses 64 bit arithmetic to circumvent issue with overflows, and
  • It always shift from 1, resulting in a lot of repeated shifts.

Anyway, the performance isn't bad at all, so let's just live with that.

One funny fact I learnt in this programming exercise is that division can lead to overflow, in particular.

$ \frac{2^{-32}}{-1} = 2^{32} $ cannot be represented as a signed int32.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/divide-two-integers/

#include "LEET_DIVIDE_TWO_INTEGERS.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

namespace _LEET_DIVIDE_TWO_INTEGERS
{
    typedef long long int64;

    class Solution {
    public:
        int64 divideHelper(int64 dividend, int64 divisor)
        {
            if (dividend < divisor)
            {
                // dividend is the remainder, if wished
                return 0;
            }
            else
            {
                int64 subtractor = divisor;
                int64 quotient = 1;
                while ((subtractor << 1) > 0 && dividend >(subtractor << 1))
                {
                    subtractor = (subtractor << 1);
                    quotient = (quotient << 1);
                }

                // At this point, we know dividend < divisor * 2
                // But in the previous iteration, we have dividend > (divisor / 2) * 2 
                // Overall, we have  divisor <= dividend < divisor * 2
                return quotient + divideHelper(dividend - subtractor, divisor);
            }
        }

        int divide(int dividend, int divisor)
        {
            int64 dividendLong = dividend;
            int64 divisorLong = divisor;

            int sign = 1;
            if (dividendLong < 0)
            { 
                sign = -sign;
                dividendLong = -dividendLong;
            }
            if (divisorLong < 0)
            {
                sign = -sign;
                divisorLong = -divisorLong;
            }
            int64 result = sign * this->divideHelper(dividendLong, divisorLong);

            int64 intMax64 = 1;
            intMax64 = intMax64 << 31;
            intMax64--;
            int intMax = (int)intMax64;

            int64 intMin64 = 1;
            intMin64 = intMin64 << 31;
            intMin64 = -intMin64;
            int intMin = (int)intMin64;

            if (result > 0)
            {
                if (result > intMax64)
                {
                    return intMax;
                }
                else
                {
                    return (int)result;
                }
            }
            else
            {
                if (result < intMin64)
                {
                    return intMin;
                }
                else
                {
                    return (int)result;
                }
            }
        }
    };
};

using namespace _LEET_DIVIDE_TWO_INTEGERS;

int LEET_DIVIDE_TWO_INTEGERS()
{
    Solution s;
    cout << s.divide(2147483647, 1) << endl;
    cout << s.divide(2147483647, 2) << endl;
    cout << s.divide(-1010369383, (1 << 31)) << endl;
    cout << s.divide((1 << 31), -1) << endl;
    return 0;
}

No comments :

Post a Comment