[Leetcode] 989. Add to Array-Form of Integer

 Problem : https://leetcode.com/problems/add-to-array-form-of-integer/description/

Add digit on each position from back. 

Time complexity = O (max(len(num), log(k))

class Solution {
    public List<Integer> addToArrayForm(int[] num, int k) {
        LinkedList<Integer> result = new LinkedList<>();
        int carry = 0;
        int i = num.length - 1;

        while (i >= 0 || k > 0 || carry != 0) {
            int a = k % 10;
            int b = i >= 0 ? num[i--] : 0;

            k /= 10;

            result.addFirst((a + b + carry) % 10);
            carry = (a + b + carry) / 10;
        }

        return result;
    }
}

[LeetCode] 415. Add Strings

 Problem: https://leetcode.com/problems/add-strings/

Simulate the process of adding 2 numbers.

class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        num1 = [int(w) for w in num1]
        num2 = [int(w) for w in num2]
        
        result = []
        carry = 0
        
        while num1 or num2:
            a = num1.pop() if num1 else 0 
            b = num2.pop() if num2 else 0
            
            c = a + b + carry
            
            result.append(c % 10)
            carry = c // 10
        
        if carry:
            result.append(carry)
        
        return ''.join([str(w) for w in reversed(result)])

[LeetCode] 781. Rabbits in Forest

 Problem : https://leetcode.com/problems/rabbits-in-forest/

Remember the last rabbit answered the same values. Then count rabbits must be in different colors.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        
        total = 0
        seen = defaultdict(int)
        
        for n in answers:
            if n == 0:
                # encounter a single rabbit of this color
                total += 1
            else:
                if seen[n+1]:
                    # encounter rabbit with same color
                    seen[n+1] -= 1
                else:
                    # encounter rabbit with different color
                    seen[n+1] += n
                    total += n+1
                    
        return total

Another math solution:

Firstly count number of rabbits anwsered the same values. For example, M rabbits answered N. Then there must be M // (N+1) group of rabbits with same color. Each group has N+1 rabbits. Additionally, there must be another group of N+1 rabbits if M % (N+1) > 0.

class Solution:
    def numRabbits(self, answers: List[int]) -> int:
        
        total = 0
        count = Counter(answers)
        
        for n, m in count.items():
            total += m // (n+1) * (n+1)
            total += n + 1 if m % (n+1) else 0
                    
        return total

[LeetCode] 390. Elimination Game

 Problem: https://leetcode.com/problems/elimination-game/

class Solution:
    def lastRemaining(self, n: int) -> int:
        # track the head number.
        # when total remaining number becomes 1, head is the only number left.
        
        left = True
        remaining = n
        
        step = 1
        head = 1 
        
        while remaining > 1:
            if left:
                # remove number from left
                # move head to next number
                head += step
            else:
                # remove number from right
                if remaining & 1:
                    # when total remaining number is odd
                    # move head to next number
                    # like 2 4 6 8 10, we move from 10, we will take out 10, 6 and 2, head is deleted and move to 4
                    head += step
                else:
                    # when total remaining number is even
                    # head won't change
                    # like 2 4 6 8 10 12, we move from 12, we will take out 12, 8, 4, head is still remaining 2
                    pass
            
            # every time remove half of the numbers
            remaining = remaining // 2
            
            # expand step
            step = step * 2
            
            # change direction
            left = not left
        
        return head

[LeetCode] 372. Super Pow

 Problem: https://leetcode.com/problems/super-pow/

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        """
        
        a = Ak + B
        b = Ck + D
        
        a * b = (Ak + B) * (Ck + D) = ACk + ADk + BCk + BD
        
        (a * b) % k = (ACk + ADk + BCk + BD) % k = BD % k
        
        a % k = B
        b % k = D
        
        (a * b) % k = (a % k) * (b % k) % k
        
        (a ** b) % k = (a * a * a .. a) % k 
                     = (a % k) * (a % k) ... * (a % k) % k
                     = (a % k) ** b % k
                     
        (a % k) % k =  a % k
        
        for a = 2, b = [1, 0]
        
        result = (2 ** (1 * 10 + 0)) % 1337 
               = (2 ** (1*10) * 2 ** 0) % 1337
               = (2 ** 1 ** 10 % 1337) * (2 ** 0  % 1337) % 1337
               = ((2 % 1337) ** 10 % 1337) * ((2 % 1337) ** 0 % 1337) % 1337
        """
        
        if not b: return 1
        
        e = b.pop()
        
        return self.myPow(self.superPow(a, b), 10) * self.myPow(a, e) % 1337 
    
    
    def myPow(self, base, exp):
        result = 1
        base = base % 1337
        
        for i in range(exp):
            result = (result * base) % 1337
            
        return result

[LeetCode] 371. Sum of Two Integers

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

This quiz is a bit of easier to solve with C language.

class Solution {
public:
    int getSum(int a, int b) {
        int c = 0;
        int carry = 0;
        
        for (int i = 0; i < 32; i ++) {
            int aa = (a >> i) & 1;
            int bb = (b >> i) & 1;
            int cc = aa ^ bb ^ carry;
                    
            carry = (aa + bb + carry) / 2;
            c = c | (cc << i);
        }
        
        return c;
    }
};

The Python solution.

class Solution:
    def getSum(self, a: int, b: int) -> int:
        c = 0
        carry = 0    
        
        for i in range(32):
            x = (a >> i) & 1
            y = (b >> i) & 1
           
            z = x ^ y ^ carry
            
            carry = x & y or x & carry or y & carry
            
            c = (z << i) ^ c
        
        return (c ^ 0x80000000) - 0x80000000

[LeetCode] 368. Largest Divisible Subset

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

For a valid subset in ascending order [A, B, C, D], if the largest number D can be divided by the Number e, then the subset [A, B, C, D, e] is still a valid subset.

Time Complexity = O ( N ** 2)

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
      int N = nums.length;

      // Maximum length of valid subset ends by the ith number,
      int[] count = new int[N];
      // Index of previous number, to which the ith number can be appended, to form the longest subset.
      int[] pre = new int[N];
      

      int maxSoFar = 0;
      int index = 0;

      Arrays.sort(nums);
      
      for (int i = 0; i < N; i++) {
        pre[i] = -1;
        count[i] = 1;
        for (int j = i - 1; j >= 0; j--) {
          if (nums[i] % nums[j] == 0) {
            // If nums[i] can be divided by nums[j], we can expend the subset ends by nums[j]
            // Because all nums[j] can be divided by all other numbers in the subset,
            // nums[i] can also be divided by other numbers in the current subset.
      
            // No need to update count[i], if nums[i] can form a longer subset with other number.
            if (count[j] + 1 > count[i]) {
              count[i] = count[j] + 1;
              pre[i] = j;
            
              if (maxSoFar < count[i]) {
                index = i;
                maxSoFar = count[i];
              }
            }
          }
        }
      }

      // Start from the last number of the longest subset and
      // iterate back to the beginner ( pre[index] == -1)
      LinkedList<Integer> result = new LinkedList<>();
      while (index != -1) {
        result.offerFirst(nums[index]);
        index = pre[index];
      }

      return result;
    }
}
        

Edited on: 04/06/2025. Add detail explanation to the steps.

[LeetCode] 365. Water and Jug Problem

 Problem : https://leetcode.com/problems/water-and-jug-problem/

This problem equals to consider there is a large container, use the 2 jugs to pour water into the container or take water out of the container, and end up with z liters water in the container.

a * x + b * y = z

Positive a / b means pour water into the container.

Negative a / b means take water out of the container.

According to Bézout's identity :  a * x + b * y =  GCD( x, y )

GCD : greatest common divisor of x and y.

So, we can get the needed liters of water when GCD( x, y ) % z == 0.

class Solution:
    def canMeasureWater(self, x: int, y: int, z: int) -> bool:
        
        def gcd(a, b):
            if a != 0:
                return gcd(b%a, a)
            else:
                return b

        if x > y:
            x, y = y, x
            
        
        return z == 0 or z <= (x + y) and y > 0 and z % gcd(x, y) == 0

[LeetCode] 357. Count Numbers with Unique Digits

 Problem : https://leetcode.com/problems/count-numbers-with-unique-digits/

The input number N means the maximum number of digits we can have for the wanted numbers.

Let F(N) = valid number of unique digits combination for N digits

F(0) = 0. Wanted number = 0. Total number = 1

F(1) = 1. Wanted number = [0 ... 9].   Total number = 10

F(2) =  9 * 9 + F (1) = 91.   The first digit has 9 options from 1 to 9. The second digit has 9 options from 0 to 9 ( excluding the digit used by the first digits)

F(3) = 9 * 9 * 8 + F(2) + F(1)

class Solution:
    def countNumbersWithUniqueDigits(self, n: int) -> int:
        if n == 0:
            return 1
        
        if n == 1:
            return 10
        
        result = 9
        digits = 9
        
        # calculate valid combiations of N digits
        for _ in range(1,n):
            result *= digits
            digits -= 1
        
        return result + self.countNumbersWithUniqueDigits(n-1)

[LeetCode] 342. Power of Four

 Problem : https://leetcode.com/problems/power-of-four/

A recursive solution :

class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        if num == 0: return False
        return num == 1 or num % 4 == 0 and self.isPowerOfFour(num // 4)

A math solution:

If N is power of 4, Log(N, base=4) is an integer.

class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        return num > 0 and log(num, 4) % 1 == 0

[LeetCode] 335. Self Crossing

 Problem : https://leetcode.com/problems/self-crossing/

There are only 3 cases can lead self-crossing.

class Solution:
    def isSelfCrossing(self, x: List[int]) -> bool:
        N = len(x)
        
        for i in range(N):
            # 4th line >= 2nd line and 1st line >= 3rd line
            if i >= 3 and x[i] >= x[i-2] and x[i-3] >= x[i-1]:
                return True
            
            # 2nd line == 4th line and 5th line >= 3rd line - 1st line
            if i >= 4 and x[i-1] == x[i-3] and x[i] >= x[i-2] - x[i-4]:
                return True
            
            # 4th line >= 2nd line and 
            # 3rd line >= 5th line and 
            # 5th line >= 3rd line - 1st line
            # and 6th line >= 4th line - 2nd line
            
            if i >= 5 and x[i-2] >= x[i-4] and \
               x[i-3] >= x[i-1] and \
               x[i-1] >= x[i-3] - x[i-5] and \
               x[i] >= x[i-2] - x[i-4]:
                return True
        
        return False

[LeetCode] 326. Power of Three

 Problem : https://leetcode.com/problems/power-of-three/

A naive solution:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 3 == 0 and self.isPowerOfThree(n // 3)

A math solution:

class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        return n > 0 and 3 ** (math.log2(n) // math.log2(3)) == n

Edited on 05/04/2021. Update the math solution.

[LeetCode] 319. Bulb Switcher

Problem : https://leetcode.com/problems/bulb-switcher/

A naive solution ( Time Limit Exceeded ).  Use bits to represent bulbs.

class Solution:
    def bulbSwitch(self, n: int) -> int:
        if n <= 0:
            return 0
        
        # turn on all bulbs
        bits = [0xFFFFFFFF] * (n // 32 + 1)
        
        for i in range(1, n):
            for j in range(i, n, i+1):
                # toggle bulbs
                bits[j//32] ^= 1 << (j%32)
        
        # count "ON" bulbs
        result = 0
        for i in range(n):
            if bits[i//32] & (1 << (i%32)):
                result += 1
        
        return result

Math solution:

Since a bulb is "OFF" initially,  a bulb ends up with "ON" state if it is switched an odd number of times.

Bulb X is switched in round Y if and only if  Y divides X ( X % Y == 0 ). 

So bulb X ends up with "ON" if and only if it has odd number of divisor.

Divisors come in pairs.  When X = 36, its divisors are (1, 36), (2, 18), (3,12), (4,9), (6,6)

So Bulb 36 will be toggled in round 1, 2, 3, 4, 6, 9, 12, 18, 36.  So Bulb 36 will be "ON" in the end.

So only square numbers have odd number of divisors.

The problem equals to count the square number between 1 to n 

class Solution:
    def bulbSwitch(self, n: int) -> int:
        result = 1
        
        while result * result <= n:
            result += 1
        
        return result - 1

[LeetCode] 273. Integer to English Words

Problem : https://leetcode.com/problems/integer-to-english-words/

Split the number into hundreds, then convert hundred into words.

class Solution:
    def numberToWords(self, num: int) -> str:
        ones = ['One', 'Two', 'Three', 'Four', \
                'Five', 'Six', 'Seven', 'Eight', \
                'Nine']
        
        odds = ['Eleven', 'Twelve',\
                    'Thirteen', 'Fourteen', 'Fifteen', 'Sixteen',\
                    'Seventeen', 'Eighteen', 'Nineteen']
        
        tens = ['Ten', 'Twenty', 'Thirty', 'Forty', 'Fifty', \
                'Sixty', 'Seventy', 'Eighty', 'Ninety']
        
        
        def hundreds(n, output):           
            if n >= 100:
                output.append(ones[(n//100) - 1])
                output.append("Hundred")
                hundreds(n%100, output)
            elif n == 10 or n >= 20:
                output.append(tens[n // 10 -1])    
                hundreds(n%10, output)          
            elif 10 < n < 20:
                output.append(odds[n - 11])
            elif n > 0:
                output.append(ones[n-1])
        
        if num == 0:
            return "Zero"
        
        output = []
        
        while num > 0:
            if num < 1000:
                hundreds(num, output)
                break
            elif 1000 <= num < 1000 * 1000:
                hundreds(num // 1000, output)
                output.append('Thousand')
                num = num % 1000
            elif 1000 * 1000 <= num < 1000 * 1000 * 1000:
                hundreds(num // (1000 * 1000), output)
                output.append('Million')
                num = num % (1000 * 1000)
            else:
                hundreds(num // (1000 * 1000 * 1000), output)
                output.append('Billion')
                num = num % (1000 * 1000 * 1000)
        
        return ' '.join(output)    

[LeetCode] 268. Missing Number

Problem : https://leetcode.com/problems/missing-number/

Hash table based solution:

Time complexity = O ( N )

Space complexity = O ( N )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        memo = set(nums)
        
        for n in nums:
            if n < len(nums) and n + 1 not in memo:
                return n + 1
        
        return 0

Bit manipulation based solution:

Time complexity = O ( N )

Space complexity = O ( 1 )

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        missing = len(nums)
    
        for i, n in enumerate(nums):
            missing ^= i ^ n
            
        return missing

As it mentioned, the numbers are from 0 to n.

Now we use all of the valid indices [0, n] to XOR with all numbers. The result is the missing number.

[LeetCode] 264. Ugly Number II

Problem : https://leetcode.com/problems/ugly-number-ii/

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        result = [1] * n
        
        l1 = l2 = l3 = 0
        i = 0
        
        for i in range(n-1):
            n1 = result[l1] * 2
            n2 = result[l2] * 3
            n3 = result[l3] * 5
            
            tmp = min(n1, n2, n3)
            if n1 == tmp:
                l1 += 1
            if n2 == tmp:
                l2 += 1
            if n3 == tmp:
                l3 += 1
        
            result[i+1] = tmp
        
        return result[-1]

An ugly number must be multiplied by either 2, 3, 5 from a smaller ugly number.

The smallest ugly number is 1. So starts from 1 and multiple to 2, 3, 5, then find the smallest as the next ugly number

A naive implementation.

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp2 = [2]
        dp3 = [3]
        dp5 = [5]
        
        i = j = k = 0

        x = 1
        
        for _ in range(1, n):
            mi = min(dp2[i], dp3[j], dp5[k])
                   
            if mi == dp2[i]:
                i += 1
                dp2.append(mi * 2)
                dp3.append(mi * 3)
                dp5.append(mi * 5)
            elif mi == dp3[j]:
                j += 1
                dp3.append(mi * 3)
                dp5.append(mi * 5)
            else:
                k += 1
                dp5.append(mi * 5)

            x = mi
            
        return x

Edited on 05/16/2021. Add the naive implementation.

[LeetCode] 263. Ugly Number

 Problem : https://leetcode.com/problems/ugly-number/

Time Complexity = O ( Log N )

class Solution:
    def isUgly(self, num: int) -> bool:
        
        if num <= 0:
            return False
        
        while num % 2 == 0:
            num = num // 2
        
        while num % 3 == 0:
            num = num // 3
        
        while num % 5 == 0:
            num = num // 5
            
        return num == 1

Use division to remove the prime factor 2, 3, 5 from the given number. Then check the remains of the number equals to 1

[LeetCode] 258. Add Digits

Problem : https://leetcode.com/problems/add-digits/

A naive solution:

class Solution:
    def addDigits(self, num: int) -> int:
        sums = 0
        
        while num > 0:
            sums += num % 10
            num = num // 10
        
        return sums if sums < 10 else self.addDigits(sums)

A mathematic solution:

class Solution:
    def addDigits(self, num: int) -> int:
        if num == 0:
            return 0
        
        return 9 if num % 9 == 0 else num % 9

Assume there is a 3 digits number   abc.

Then abc = a * 100 + b * 10 + c

Let sums =  a + b + c,  then  abc - sums = 99 * a + 9 * b

So, sums = abc - (99 * a  +  9 *b) 

Because  (99 * a + 9 * b)  is divisible by 9,     sums % 9 = abc % 9.

So we return  num % 9 as result.  If num % 9 = 0,  return 9.  As we only need to repeatedly add all digits until the result has only one digit.

[LeetCode] 233. Number of Digit One

Problem : https://leetcode.com/problems/number-of-digit-one/

class Solution:
    def countDigitOne(self, n: int) -> int:
        result, a, b = 0, 1, 1
        
        while n > 0:
            result += (n + 8) // 10 * a
            if n % 10 == 1:
                result += b
                
            b += n % 10 * a
            a *= 10
            
            n //= 10
            
        
        return result

[LeetCode] 231. Power of Two

Problem : https://leetcode.com/problems/power-of-two/

Iteration solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        while n > 1:
            if n % 2 != 0:
                return False

            # n = n // 2
            n = n >> 1
           
        return n == 1

Recursion solution:

Time complexity = O ( Log N )

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n <= 0:
            return False
        
        if n == 1:
            return True
        
        return n % 2 == 0 and self.isPowerOfTwo(n >> 1)

Bit manipulate solution:

Time complexity = O ( 1 )

 
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:   
        
        count = 0
        while n > 0 and count <= 1:
            count += n & 1
            n >>= 1
        
        return count == 1

Number may have only one bit equals to 1 if it is power of 2.

With that observation in mind, we have the one liner solution:

n & (n-1) can trim the first '1' bit from right.

n & (n-1) == 0 means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:    
        return n > 0 and (n - 1) & n == 0

n & (-n) can extract the firt '1' bit from right.

n & (-n) == n also means number n only as one '1' bit.

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and n & (-n) == n

Edited on 05/03/2021. Add the one liner solution.

Edited on 11/07/2021. Add the second one liner solution base on bit manipulation.