diff options
author | Jack Sangdahl <[email protected]> | 2025-01-07 16:53:21 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-07 16:53:21 +0100 |
commit | 8a2b42fc8d607c983f5ce0f746253441fe7c38c4 (patch) | |
tree | f0e97dd4df910249429f516b97f60c8261d242a9 | |
parent | f456a519266258e8f392e183bc9e1bc399942dca (diff) | |
download | leetcode-8a2b42fc8d607c983f5ce0f746253441fe7c38c4.tar.gz leetcode-8a2b42fc8d607c983f5ce0f746253441fe7c38c4.zip |
29. divide two integers
-rw-r--r-- | divide_2_int.c | 32 | ||||
-rw-r--r-- | divide_2_int.cpp | 32 | ||||
-rw-r--r-- | divide_2_int.py | 32 |
3 files changed, 64 insertions, 32 deletions
diff --git a/divide_2_int.c b/divide_2_int.c new file mode 100644 index 0000000..0e4e754 --- /dev/null +++ b/divide_2_int.c @@ -0,0 +1,32 @@ +// 29. Divide Two Integers +#include "leetcode.h" + +/* + * Given two integers 'dividend' and 'divisor', divide two integers without + * using multiplication, division, or mod operations. the integer division + * should truncate toward zero, which means losing its fractional part. for + * example, 8.345 would be truncated to 8. return the quotient after dividing + * 'dividend' by 'divisor'. + */ + +int divide(int dividend, int divisor) { + if (dividend == INT_MIN && divisor == -1) + return INT_MAX; + long dvd = labs(dividend), dvs = labs(divisor), ans = 0; + int sign = dividend > 0 ^ divisor > 0 ? -1 : 1; + while (dvd >= dvs) { + long temp = dvs, m = 1; + while (temp << 1 <= dvd) { + temp <<= 1; + m <<= 1; + } + dvd -= temp; + ans += m; + } + return sign * ans; +} + +int main() { + printf("%d\n", divide(10, 3)); // expect: 3 + printf("%d\n", divide(7, -3)); // expect: -2 +} diff --git a/divide_2_int.cpp b/divide_2_int.cpp deleted file mode 100644 index 7c172f7..0000000 --- a/divide_2_int.cpp +++ /dev/null @@ -1,32 +0,0 @@ -#include <bits/stdc++.h> - -class Solution { -public: - int divide(int dividend, int divisor) { - if (dividend == divisor) { - if (divisor == -1) - return INT_MAX; - else if (divisor == INT_MIN) - return 1; - else if (divisor < 0) - return 1 + divide(dividend - divisor, divisor); - else - return -1 + divide(dividend + divisor, divisor); - } else if (divisor == INT_MIN) - return 0; - bool negative = (dividend < 0) ^ (divisor < 0); - dividend = abs(dividend); - divisor = abs(divisor); - int result = 0; - for (int i = 31; i >= 0; --i) { - int shiftedDiv = (dividend >> i); - if (shiftedDiv >= divisor) { - result += (1 << i); - dividend -= (divisor << i); - } - } - return (negative ? -result : result); - } -}; - -int main() {} diff --git a/divide_2_int.py b/divide_2_int.py new file mode 100644 index 0000000..8439a1b --- /dev/null +++ b/divide_2_int.py @@ -0,0 +1,32 @@ +# 29. Divide Two Integers + +""" +Given two integers 'dividend' and 'divisor', divide two integers without +using multiplication, division, or mod operations. the integer division +should truncate toward zero, which means losing its fractional part. for +example, 8.345 would be truncated to 8. return the quotient after dividing +'dividend' by 'divisor'. +""" + + +class Solution(object): + def divide(self, dividend, divisor): + """ + :type dividend: int + :type divisor: int + :rtype: int + """ + if dividend == -2147483648 and divisor == -1: + return 2147483647 + dvd, dvs, ans = abs(dividend), abs(divisor), 0 + for i in range(32)[::-1]: + if (dvd >> i) - dvs >= 0: + ans += 1 << i + dvd -= dvs << i + return ans if (dividend > 0) == (divisor > 0) else -ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.divide(dividend=10, divisor=3)) + print(obj.divide(dividend=7, divisor=-3)) |