My accepted c++ solution without long long, 10ms.


  • 1
    class Solution {
    public:
        int divide(int dividend, int divisor) {
    		if (divisor == INT_MIN)
    			return dividend == divisor ? 1 : 0;
    		else if (!divisor || divisor == -1 && dividend == INT_MIN)
    			return INT_MAX;
    		else if (divisor == 1)
    			return dividend;
    		bool negative = (dividend > 0) ^ (divisor > 0);
    		if (dividend > 0)
    			dividend = -dividend;
    		if (divisor > 0)
    			divisor = -divisor;
            std::vector<int> multipliers, products;
    		multipliers.push_back(1);
    		products.push_back(divisor);
    		int idx = 1, res = 0;
            while (products[idx - 1] < 0 && idx < 32) {
    			products.push_back(divisor << idx);
    			multipliers.push_back(1 << idx);
    			++idx;
    		}
    		idx -= 2;
    		while (dividend <= divisor) {
                if (dividend <= products[idx]) {
                    res += multipliers[idx];
                    dividend -= products[idx];
                }
    			--idx;
    		}
    		return negative ? -res : res;
        }
    };

Log in to reply
 

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