aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-07 16:53:21 +0100
committerJack Sangdahl <[email protected]>2025-01-07 16:53:21 +0100
commit8a2b42fc8d607c983f5ce0f746253441fe7c38c4 (patch)
treef0e97dd4df910249429f516b97f60c8261d242a9
parentf456a519266258e8f392e183bc9e1bc399942dca (diff)
downloadleetcode-8a2b42fc8d607c983f5ce0f746253441fe7c38c4.tar.gz
leetcode-8a2b42fc8d607c983f5ce0f746253441fe7c38c4.zip
29. divide two integers
-rw-r--r--divide_2_int.c32
-rw-r--r--divide_2_int.cpp32
-rw-r--r--divide_2_int.py32
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))