# Weekly Contest 393
日期：2024/04/14

這次我只有解前兩題。第三題是 Hard (Medium+) 的題目，從評論區來看，解題的人都是從題目給的限制去推測解題方式，第四題我完全沒看。

此次題目：
- [3114. Latest Time You Can Obtain After Replacing Characters](https://leetcode.com/problems/latest-time-you-can-obtain-after-replacing-characters/description/)
- [3115. Maximum Prime Difference](https://leetcode.com/problems/maximum-prime-difference/description/)
- [3116. Kth Smallest Amount With Single Denomination Combination](https://leetcode.com/problems/kth-smallest-amount-with-single-denomination-combination/description/)
- [3117. Minimum Sum of Values by Dividing Array](https://leetcode.com/problems/minimum-sum-of-values-by-dividing-array/description/)

#### 第一題

直接把所有條件列出後修改即可

class Solution {
public:
    string findLatestTime(string s) {
        const char q = '?';
        if(s[0] == q) {
            if(s[1] == q) {
                s[0] = '1';
                s[1] = '1';
            }else{
                if(s[1] == '1' || s[1] == '0')
                    s[0] = '1';
                else
                    s[0] = '0';
            }
        }else{
            if(s[1] == q) {
                if(s[0] == '0')
                    s[1] = '9';
                else if(s[0] == '1')
                    s[1] = '1';
            }
        }
        
        
        if(s[3] == q) {
            s[3] = '5';
        }
        
        if(s[4] == q)
            s[4] = '9';
        return s;
    }
};

#### 第二題
大概是 Easy 題目改編而來

class Solution {
public:
    unordered_set<int> prime_table;
    void generate_prime() {
        vector<int>gg = {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};
        for(int x: gg)
            prime_table.insert(x);
    }
    
    bool is_prime(int x) {
        return prime_table.find(x) != prime_table.end();
    }
    
    int maximumPrimeDifference(vector<int>& nums) {
        const int n = nums.size();
        generate_prime();
        int i = 0;
        int j = n - 1;
        while(!is_prime(nums[i]))
            i++;

        while(!is_prime(nums[j]))
            j--;
        
        return j - i;
    }
};

#### 第三題

看完題目敘述，如果是按到題目敘述解題，可以用 `unordered_set` 硬解題目，只是一定會超時。

我只想到這是一個數數問題(counting problem)，可以用以下式子，去數第 k 個是什麼數值，但我想不到轉換的函式。
圖片來自：[Wikipedia](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle)

從討論區中，提供了 Python 版本的計算方式：
- [[Python3] Math | Inclusion-Exclusion Principle | Binary Search](https://leetcode.com/problems/kth-smallest-amount-with-single-denomination-combination/solutions/5019504/python3-math-inclusion-exclusion-principle-binary-search/)
- [Binary Search Solution | Python](https://leetcode.com/problems/kth-smallest-amount-with-single-denomination-combination/solutions/5020415/binary-search-solution-python/)

例如以題目範例 `coins = [2, 5]`，如果問 20 是第幾個數字：
- 對於 2，20 是第 10 個數字；對於 5，是第 4 個數字。
- 當中 10 這個數字重複計算兩次，對於 `10`，可以以 `20 / 10 = 2` 求出。其中 `10` 可以用最小公倍數求出。

這樣就能將數值轉換成第幾個，並透過 Binary Search 找到對應的 `k`，即為解答。

def findKthSmallest(coins: list[int], k: int) -> int:
    N = len(coins)

    def count(num: int) -> int:
        total, add_ = 0, True
        for i in range(1, N + 1):
            curr = 0
            for comb in itertools.combinations(coins, r=i):
                curr += num // math.lcm(*comb)
            total = total + curr if add_ else total - curr
            add_ = not add_

        return total

    # Binary search
    # Result must be lesser than: lowest denomination * k
    low = min(coins)
    high = low * k
    while low <= high:
        mid = (low + high) // 2
        k_ = count(mid)
        if k_ < k:
            low = mid + 1
        else:
            high = mid - 1

    return low