23.03.29 Today’s Leetcode

554. Brick Wall (medium)

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        n = len(wall)
        temp = defaultdict(int)
        for i in range(n):
            cur = 0
            for j in range(len(wall[i]) - 1):
                cur += wall[i][j]
                temp[cur] += 1
        
        print(temp)
        return n - max(temp.values()) if temp else n

1735. Count Ways to Make Array With Product (hard)

TLE : 53/67

class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        mod = 10 ** 9 + 7
        dp = defaultdict(dict)
        def help(n, k):
            if n == 1:
                return 1
            if k in dp[n]:
                return dp[n][k]
            res = 0
            for i in range(1, k + 1):
                if k % i == 0:
                    res += help(n - 1, k // i)
                    res %= mod
            dp[n][k] = res
            return res
        return [help(x, y) for x, y in queries]

Mathmatical Approach

primes = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97)
class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        def nK(n: int, k: int) -> int:
            res = 1
            # 3, 12
            for p in primes:
                r = 0
                while k % p == 0:
                    r += 1
                    k /= p
                res *= comb(n - 1 + r, r)
            if (k != 1):
                res *= n            
            return res % 1000000007
            
        return [nK(n, k) for n, k in queries]

2523. Closest Prime Numbers in Range (medium)

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        def isPrime(n):
            if n < 2: return False
            for i in range(2, int(n**0.5) + 1):
                if n % i == 0:
                    return False
            return True
        
        prev = -1
        distance = float('inf')
        res = [-1, -1]
        for i in range(left, right + 1):
            if isPrime(i):
                # print(prev, i)
                if prev > 0 and i - prev < distance:
                    res = [prev, i]
                    distance = i - prev
                    if distance <= 2: return res
                prev = i
        return res

Long Time No See Mr.JAVA!

class Solution {
    public boolean isPrime(int n) {
        if (n == 1)
            return false;
        for (int i = 2; i <= Math.sqrt(n); ++i)
            if (n % i == 0)
                return false;
        return true;
    }

    public int[] closestPrimes(int left, int right) {
        int[] res = new int[]{-1, -1};
        int dist = 100000000;
        int prev = -1;
        for (int i = left; i <= right; ++i) {
            if (!isPrime(i))
                continue;
            if (prev > 0 && i - prev < dist) {
                dist = i - prev;
                res = new int[]{prev, i};
            }
            prev = i;
        }
        return res;
    }
}

1402. Reducing Dishes (hard)

class Solution:
    def maxSatisfaction(self, satisfaction: List[int]) -> int:
        d = sorted(satisfaction)
        n = len(d)
        print(d)
        def help(arr, start):
            num = 0
            time = 1
            for index in range(start, n):
                num += time * d[index]
                time += 1
            return num
        
        res = 0
        for i in range(n):
            res = max(res, help(d, i))
        
        return res