11 posts tagged with "Math"

from typing import Callable


class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack: list[int] = []
        operators: dict[str, Callable[[int, int], int]] = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a / b),
        }
        for token in tokens:
            if token in operators:
                b, a = stack.pop(), stack.pop()
                stack.append(operators[token](a, b))
            else:
                stack.append(int(token))
        return stack[0]

'''
f(k) = (n/k)^k
-> ln(f(k)) = k ln(n/k)
-> d ln(f(k)) / d k = ln(n/k) + k(-1/k)
-> d f(k) / f(k) d k = ln(n/k) - 1
-> f′(k) = f(k) (ln(n/k) - 1)
find the maximum:
f′(k) = 0
-> ln(n/k) = 1
-> n/k = e, 2 or 3
'''


import math


class Solution1:  # O(n)
    # https://leetcode.com/problems/integer-break/solutions/4136961/easy-olog-n-time-with-o1-space-complexity-easy-math-solution-with-proofs/
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        result = 1
        while n > 4:
            result *= 3
            n -= 3
        return n * result


class Solution2:  # O(log(n))
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return 2 ** (-n % 3) * 3 ** ((n - 4) // 3 + (n - 1) % 3)


class Solution:  # O(1)
    def integerBreak(self, n: int) -> int:
        if n < 4:
            return n - 1
        return int(math.pow(2, -n % 3) * math.pow(3, (n - 4) // 3 + (n - 1) % 3))

class Solution1:
    def rotate(self, nums: list[int], k: int) -> None:
        if len(nums) > 1:
            k %= len(nums)
            nums[:-k], nums[-k:] = nums[-k:], nums[:-k]


class Solution:
    def rotate(self, nums: list[int], k: int) -> None:
        def reverse(start, stop):
            for i in range((stop - start) // 2):
                l, r = start + i, stop - 1 - i
                nums[l], nums[r] = nums[r], nums[l]

        k %= len(nums)
        reverse(0, len(nums) - k)
        reverse(len(nums) - k, len(nums))
        reverse(0, len(nums))

class Solution:
    def accountBalanceAfterPurchase(self, purchaseAmount: int) -> int:
        return 100 - (purchaseAmount + 5) // 10 * 10

from ..notes import gcd


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def insertGreatestCommonDivisors(self, head: ListNode) -> ListNode:
        node = head
        while node.next:
            node.next = ListNode(val=gcd(node.val, node.next.val), next=node.next)
            node = node.next.next
        return head

class Solution1:
    def getSum(self, a: int, b: int) -> int:
        MASK, xor, carry = 1023, a ^ b, (a & b) << 1
        if carry & MASK:
            return self.getSum(xor, carry)
        return xor & MASK if carry else xor


class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 1023
        while b & MASK:
            a, b = a ^ b, (a & b) << 1
        return a & MASK if b else a

class Solution:
    def arraySign(self, nums: list[int]) -> int:
        sig = True
        for num in nums:
            if num == 0:
                return 0
            if num < 0:
                sig = not sig
        return int(sig or -1)

from math import isqrt


class Solution:
    def bulbSwitch(self, n: int) -> int:
        '''
        -> find the amount number of intergers that have odd number of factors
        -> only the square numbers have odd number of factors
        -> find the max number that number's square <= n
        '''
        for i in range(n):
            if (i + 1) ** 2 > n:
                return i
        return n


class Solution0:
    def bulbSwitch(self, n: int) -> int:
        return int(n**0.5)


class Solution2:
    def bulbSwitch(self, n: int) -> int:
        return isqrt(n)

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        ZERO = '0'
        if ZERO in (num1, num2):
            return ZERO

        def ord_(x):
            return ord(x) - ord(ZERO)

        def chr_(x):
            return chr(x + ord(ZERO))

        L1, L2 = len(num1) - 1, len(num2) - 1
        result = []
        carry = 0
        i = 0
        while (i <= L1 + L2) or carry:
            j = max(0, i - L2)
            while j <= min(i, L1):
                n1, n2 = num1[L1 - j], num2[L2 - i + j]
                carry += ord_(n1) * ord_(n2)
                j += 1
            result.append(chr_(carry % 10))
            carry //= 10
            i += 1
        return ''.join(result)[::-1]

class Solution:
    def isHappy(self, n: int) -> bool:
        visiteds = set()
        while n not in visiteds:
            if n == 1:
                return True
            visiteds.add(n)
            n = sum(int(x) ** 2 for x in str(n))
        return False

class Solution:
    def computeArea(
        self,
        ax1: int,
        ay1: int,
        ax2: int,
        ay2: int,
        bx1: int,
        by1: int,
        bx2: int,
        by2: int,
    ) -> int:
        (ax1, ax2), (ay1, ay2), (bx1, bx2), (by1, by2) = map(
            sorted,
            ((ax1, ax2), (ay1, ay2), (bx1, bx2), (by1, by2)),
        )
        return sum(
            (
                (ax2 - ax1) * (ay2 - ay1),
                (bx2 - bx1) * (by2 - by1),
                -(
                    max(0, min(ax2, bx2) - max(ax1, bx1))
                    * max(0, min(ay2, by2) - max(ay1, by1))
                ),
            )
        )