5 - Interesting Solutions -> Python
\n#-------------------------------------------------------\n# Range Limiting Method --> Accepted Solution.\n#---------------------------------------------------
```\n#-------------------------------------------------------\n# Range Limiting Method --> Accepted Solution.\n#-------------------------------------------------------\nclass Solution(object):\n    def getSum(self, a: int, b: int) -> int:\n        """\n        :type a: int\n        :type b: int\n        :rtype: int\n        """\n        # 32 bits integer max\n        MAX = 0x7FFFFFFF\n        # 32 bits interger min\n        MIN = 0x80000000\n        # mask to get last 32 bits\n        mask = 0xFFFFFFFF\n        while b != 0:\n            # ^ get different bits and & gets double 1s, << moves carry\n            a, b = (a ^ b) & mask, ((a & b) << 1) & mask\n        # if a is negative, get a\'s 32 bits complement positive first\n        # then get 32-bit positive\'s Python complement negative\n        return a if a <= MAX else ~(a ^ mask)\n\n\n\n#-------------------------------------------------------\n#       Memory Limit Exceeded Solution.\n#-------------------------------------------------------\nclass Solution:\n    def getSum(self, a: int, b: int) -> int:\n        if b == 0:\n            return a\n        else:\n            return self.getSum(a ^ b, (a & b) << 1)\n\t\t\t\n\n#-------------------------------------------------------\n#       Time Limit Exceeded Solution.\n#-------------------------------------------------------\nclass Solution:\n    def getSum(self, a: int, b: int) -> int:\n        carry = 0\n        while b != 0:\n            carry = a & b\n            a = a ^ b\n            b = carry << 1\n        return a\n\n\n#-------------------------------------------------------\n#       Joke LoopHole Solution.\n#-------------------------------------------------------\nclass Solution(object):\n\tdef getSum(self, a: int, b: int) -> int:\n\t\t"""\n\t\t:type a: int\n\t\t:type b: int\n\t\t:rtype: int\n\t\t"""\n\t\tlist=[a,b]\n\t\treturn sum(list)\n```\n\n**Most Time Efficient Solution**\n```\nclass Solution:\n    def getSum(self, a: int, b: int) -> int:\n        \'\'\'\n            Problem: We want to add 2 numbers without using the + or -\n                     operators.\n            \n            Solution: We can use bit-wise manipulation but\n                     we need to write down all the possible cases:\n                        a: +  b: +  \n                        a: -  b: -\n                        a: +  b: - \n                        b: -  b: +\n                    \n                    For all problems:\n                        1. We automatically do all our calculations with abs(a) and abs(b)\n                            a, b = abs(a), abs(b)\n                        2. We always ensure that abs(a) < abs(b), otherwise we switch a/b\n                        \n                    SubProblem - 1: a + b\n                        We can use the algorithm in I, where we contiously update sumNoCarry and carry\n                        until carry = 0.\n                        \n                         while carry = 0      \n                            sumNoCarry = a & b            =   a + b (w/o carry)\n                            carry = (a ^ b) << 1          =   carry       \n                            a, b = sumNoCarry, carry      =   a + b + carry\n                \n                            \n                    SubProblem-2: -a + (-b)\n                        We can use the algorithm in I, where we contiously update sumNoCarry and carry\n                        until carry = 0. Because python keeps track of negative indices\n                    \n                    SubProblem-3 & SubProblem-4: a - b  OR  b - a\n                        If we have subtraction, we use borrow instead, where we use NOT to invert the given number\n                        while borrow = 0\n                            sumNoBorrow = a & b         = a - b (w/o carry)\n                            borrow = (~a * b) << 1      = borrow\n                            a, b, = sumNoBorrow, borrow = a - b + borrow\n            \n            Time: O(1) because each integer contains 32 bits.\n            Space: O(1) because we don\'t use any additional data structures.\n                        \n            WhiteBoard:\n                I: a * b > 0    [+a,+b] OR [-a, -b]\n                \n                    --- iteration 1 ---\n                    a = 15          01111 \n                    b = 2           00010   \n                    a + b = 17      10001       [SOLUTION]\n                    a ^ b           01101        = sum w/o carry (a)\n                    a & b           00010        \n                    (a&b) << 1      00100        = carry (b)\n\n\n                    Solution = (a^b) + ((a&b) << 1) = (01101 + 00100) = 10101\n                        The sub-problem is the same as the problem, so we can use a loop\n                        The base-case would be when our carry = 0\n\n                    --- iteration 2 ---\n                    a =  x & y           01101   = 13   \n                    b = (x&y) << 1       00100   = 4\n\n                    x = 13      01101\n                    y = 4       00100\n                    x^y         01001       = sum w/o carry(a)\n                    x&y         00100\n                    (x^y)<<1    01000       = carry (b)\n                \n                    \n                    --- iteration 3 ---\n                    a =  x & y           01001   = 9  \n                    b = (x&y) << 1       01000   = 8\n\n                    x = 9       01001\n                    y = 8       01000\n                    x^y         00001       = sum w/o carry(a)\n                    x&y         01000\n                    (x^y)<<1    10000       = carry (b)\n                    \n                      --- iteration 3 ---\n                    a =  x & y           00001   = 1\n                    b = (x&y) << 1       10000   = 16\n                    \n                    x = 16      00001\n                    y = 4       10000\n                    x^y         10001       = sum w/o carry(a)\n                    (x^y)<<1    00000       = carry (b)\n                    \n                    carry = 0, so we return 10001 = 10101 = 17\n                 \n                II: a * b < 0    [-a,+b] OR [a, -b]\n                    --- iteration 1 ---\n                    a = -16      1..10000   MSB = flag for +/-\n                    b = 15          01111 \n                    a + b = 13   1..00001       [SOLUTION]\n                    a = abs(a)      10000\n                    a ^ b           11111   =  31 <-------------- SUM W/O CARRY ---\n                    ~a =         1..10001   = -17\n                       =         0..01110     <-- 1. Flipped\n                       =         0..01111     <-- 2. Add 1\n                    (~a&b)       0..01111   =  15  \n                    (~a&b)<<1       11110   = 15 * 2^2 = 30   <---- CARRY ----\n                    \n                     --- iteration 2 ---\n                    a =  a ^ b           011111   = 31 \n                    b = (~a&b) << 1      011110   = 30\n                    a ^ b                000001   = 1\n                    ~a                0..100000   = -32\n                                      1..011111   <-- Flip\n                                      1..100000   <-- Add 1\n                    (~a & b)                0\n                    \n                        return -1\n                    \n                                    \n                0b10001\n                0b01111\n                  1111\n\n                    Solution = (a^b) + ((a&b) << 1) = (01101 + 00100) = 10101\n                        The sub-problem is the same as the problem, so we can use a loop\n                        The base-case would be when our carry = 0\n\n\n                \n            \n        \'\'\'\n        # 0. Get the absolutes values of both numbers\n        absA, absB = abs(a), abs(b)\n        \n        # 1. Ensure that abs(a) >= abs(b)\n        if absA < absB:\n            return self.getSum(b, a)\n        \n        # 2. Store the sign - it will negative if the greater number if negative (a will always be greater)\n        sign = -1 if a < 0 else 1\n                \n        # 3. Perform bit-wise operations to compute the sum\n        # 3a. If both a & b have the same sign [+a, +b] OR [-a, -b]\n        if a * b >= 0:\n            # Continue looping until the amount to carry (b) is 0\n            while absB:\n                # Calculate the sum without carry using XOR\n                sumWithoutCarry = absA ^ absB\n                # Calculate the amount to carry using AND and a left-wise shift\n                carry = (absA & absB) << 1\n                # We are now left with a sub-problem where sum = sumWithoutCarry + carry\n                absA, absB = sumWithoutCarry, carry\n        \n        # 3b. a & b have different signs [-a, +b] OR [+a, -b]\n        else:\n            # Continue looping until the amount to borrow (b) is 0\n            while absB:\n                # Calculate the sum w/o borrow using XOR\n                sumWithoutBorrow = absA ^ absB\n                # Calculate the amount to borrow using NOT, AND and a left-wise shift\n                borrow = (~absA & absB) << 1\n                # We are now left with a sub-problem where sum = sumWithoutBorrow + borrow\n                absA, absB = sumWithoutBorrow, borrow\n        \n        # 4. Return the solution\n        return sign * absA\n```\n\n
['Python']