29. Divide Two Integers[M]

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

Description

iven two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

1
2
3
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

1
2
3
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

Solution

1

371. Sum of Two Integers

https://leetcode.com/problems/sum-of-two-integers/

Description

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

1
2
Input: a = 1, b = 2
Output: 3

Example 2:

1
2
Input: a = -2, b = 3
Output: 1

Solution

hahaha

1
2
3
class Solution:
    def getSum(self, a: int, b: int) -> int:
        return sum([a,b])
1
2
3
class Solution:
    def getSum(self, a: int, b: int) -> int:
        return operator.add(a, b)

Ok, that’s ridiculous and cheating, ok, now do it without using pre-defined functionslet us dive into the bit operators.

https://leetcode.com/problems/sum-of-two-integers/discuss/84278/A-summary%3A-how-to-use-bit-manipulation-to-solve-problems-easily-and-efficiently

https://leetcode.com/problems/sum-of-two-integers/discuss/84282/Python-solution-with-no-%22%2B-*%22-completely-bit-manipulation-guaranteed

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def getSum(self, a: int, b: int) -> int:
        # 32 bits integer max
        MAX = 0x7FFFFFFF
        # 32 bits interger min
        MIN = 0x80000000
        # mask to get last 32 bits
        mask = 0xFFFFFFFF
        while b != 0:
            # ^ get different bits and & gets double 1s, << moves carry
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
        # if a is negative, get a's 32 bits complement positive first
        # then get 32-bit positive's Python complement negative
        return a if a <= MAX else ~(a ^ mask)

https://leetcode.com/discuss/111582/java-simple-easy-understand-solution-with-explanation

https://leetcode.com/discuss/111705/one-positive-one-negative-case-successful-for-python-rules

In Python this problem is much different because of the negative number.

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def getSum(self, a: int, b: int) -> int:
        import ctypes
        sum = 0
        carry = ctypes.c_int32(b)
        while carry.value:
            sum = a ^ carry.value
            carry = ctypes.c_int32(a & carry.value)
            carry.value <<= 1
            a = sum
        return sum

69. Sqrt(x)[E]

https://leetcode.com/problems/sqrtx/

Description

implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

1
2
Input: 4
Output: 2

Example 2:

1
2
3
4
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Solution

1
2
3
class Solution:
    def mySqrt(self, x: int) -> int:
        return int(math.sqrt(x))
1
2
3
4
5
6
7
8
9
10
class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x < 4:
            return 1
        res = 2 * self.mySqrt(x / 4)
        if (res + 1) * (res + 1) <= x and (res + 1) * (res + 1) >= 0:
            return res + 1
        return  res

166. Fraction to Recurring Decimal[M]

https://leetcode.com/problems/fraction-to-recurring-decimal/

Description

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

1
2
Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

1
2
Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

1
2
Input: numerator = 2, denominator = 3
Output: "0.(6)"

Solution

1

368. Largest Divisible Subset[M]

https://leetcode.com/problems/largest-divisible-subset/

Description

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:

Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:

1
2
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)

Example 2:

1
2
Input: [1,2,4,8]
Output: [1,2,4,8]

Solution

1