Вопрос. Даны два целых числа dividend и divisor. Разделите два целых числа без использования операций умножения, деления и модификатора.

Верните частное после деления dividend на divisor.

Целочисленное деление должно усекаться до нуля.

Пример 1:

Input: dividend = 10, divisor = 3
Output: 3

Пример 2:

Input: dividend = 7, divisor = -3
Output: -2

Примечание.

  • И делимое, и делитель будут 32-битными целыми числами со знаком.
  • Делитель никогда не будет равен 0.
  • Предположим, что мы имеем дело со средой, которая может хранить целые числа только в диапазоне 32-битных целых чисел со знаком: [−231, 231 − 1]. Для решения этой задачи предположим, что ваша функция возвращает 231 − 1, когда результат деления переполняется.

Полностью вопрос можно посмотреть здесь.

Подход 1. Как обычно, начнем с чего-то прямолинейного и наивного. Умножение - это многократное сложение. Отсюда мы можем прийти к следующему коду —

//Approach 1:
//RunTime: Time Limit Exceeded
//Memory usage: N/A
class Solution {
    public int divide(int dividendI, int divisorI) {
        int sign = 1;
        int signD = 1;
        double dividend = dividendI;
        double divisor = divisorI;
        if(divisor<0){
            sign = -1;
            divisor*=-1;
        }
        if(dividend<0){
            signD = -1;
            dividend*=-1;
        }
        int q = 0;
        if(divisor==1){
            double result = dividend*sign*signD;
            if(result>Integer.MAX_VALUE || result<Integer.MIN_VALUE){
                return Integer.MAX_VALUE;
            }
            
            return (int)result;
        }
        while(dividend>=divisor){
            dividend-=divisor;
            q++;
        }
        return q*sign*signD;
    }
}

Очевидно, нам предстоит долгий путь.

Подход 2. После нескольких часов тяжелого труда нам стало лучше . Еще в школе, помните, как мы делали деление в столбик. Следующий код делает именно это для нас —

//Approach 2:
//Runtime: 1ms
//Memory usage: 32.5MB
class Solution {
    public int divide(int dividend, int divisorI) {
        int signDs = getSign(divisorI);
        int signDd = getSign(dividend);
        double divisor = (double)divisorI * signDs;
        
        double q = 0;
        double rem = 0;
        char[] chars = String.valueOf(dividend).toCharArray();
        for(char c : chars){
            if(c=='-'){
                continue;
            }
            rem = rem * 10 + (c - '0');
            int tempQ = 0;
            while(rem>=divisor){
                tempQ++;
                rem-=divisor;
            }
            q=q*10 + tempQ;
        }
        if(q*signDs*signDd > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        return (int)(q*signDs*signDd);
    }
    
    private int getSign(int num){
        if(num<0){
            return -1;
        }
        return 1;
    }
}

Больше постов ищите здесь.

Удачи и Чао!