Make Sum Divisible by P (LeetCode 1590)

Nguồn: LeetCode 1590 Độ khó: Trung bình (Medium) Prefix sum Chia lấy dư Map

Đề bài

🇻🇳 Tiếng Việt🇬🇧 English (đề gốc)

1590. Make Sum Divisible by P – Làm cho tổng chia hết cho P (LeetCode, độ khó Medium)

Cho một mảng các số nguyên dương nums, hãy xóa đi đoạn con ngắn nhất (có thể rỗng) sao cho tổng các phần tử còn lại chia hết cho p. Không được phép xóa toàn bộ mảng.

Hãy trả về độ dài của đoạn con ngắn nhất cần xóa, hoặc -1 nếu không thể làm được.

Đoạn con (subarray) là một khối các phần tử liên tiếp trong mảng.

Ràng buộc:

• $1 \le$ nums.length $\le 10^5$
• $1 \le$ nums[i] $\le 10^9$
• $1 \le p \le 10^9$

Định dạng vào/ra để chạy thử trên máy: trên LeetCode các bạn chỉ cần viết hàm minSubarray trong class Solution. Để chạy như một chương trình bình thường (và dùng khung chạy tay bên dưới), mình đặt thêm định dạng:

• Dữ liệu vào: dòng đầu gồm 2 số nguyên $n$ (số phần tử) và $p$, dòng thứ hai gồm $n$ số nguyên nums[0], nums[1], ..., nums[n-1].
• Kết quả: một số nguyên là đáp án của bài.

Ví dụ 1

Input: nums = [3,1,4,2],
       p = 6
Output: 1
---stdin---
4 6
3 1 4 2

Tổng các phần tử là 10, không chia hết cho 6. Ta có thể xóa đoạn con [4], tổng các phần tử còn lại là 6, chia hết cho 6.

Ví dụ 2

Input: nums = [6,3,5,2],
       p = 9
Output: 2
---stdin---
4 9
6 3 5 2

Không thể xóa một phần tử duy nhất mà được tổng chia hết cho 9. Cách tốt nhất là xóa đoạn con [5,2], còn lại [6,3] có tổng là 9.

Ví dụ 3

Input: nums = [1,2,3],
       p = 3
Output: 0
---stdin---
3 3
1 2 3

Tổng là 6, đã chia hết cho 3 rồi nên không cần xóa gì cả.

Ví dụ 4

Input: nums = [1,2,3],
       p = 7
Output: -1
---stdin---
3 7
1 2 3

Không có cách xóa đoạn con nào để được tổng chia hết cho 7.

Ví dụ 5

Input: nums = [1000000000,
               1000000000,
               1000000000],
       p = 3
Output: 0
---stdin---
3 3
1000000000 1000000000 1000000000

1590. Make Sum Divisible by P (LeetCode, Medium)

Given an array of positive integers nums, remove the smallest subarray (possibly empty) such that the sum of the remaining elements is divisible by p. It is not allowed to remove the whole array.

Return the length of the smallest subarray that you need to remove, or -1 if it's impossible.

A subarray is defined as a contiguous block of elements in the array.

Example 1:

Input: nums = [3,1,4,2], p = 6
Output: 1
Explanation: The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

Example 2:

Input: nums = [6,3,5,2], p = 9
Output: 2
Explanation: We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

Example 3:

Input: nums = [1,2,3], p = 3
Output: 0
Explanation: Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

Example 4:

Input: nums = [1,2,3], p = 7
Output: -1
Explanation: There is no way to remove a subarray in order to get a sum divisible by 7.

Example 5:

Input: nums = [1000000000,1000000000,1000000000], p = 3
Output: 0

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 1 <= p <= 10^9

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lưu ý nhỏ: khi nộp trên CLUE OJ các bạn dán toàn bộ code, gồm cả hàm main, vì đề trên CLUE OJ đọc dữ liệu vào và in kết quả đúng theo định dạng ở phần đề bài, giống như khi các bạn chạy thử trên máy hoặc ở trang Chạy code online của blog.

Tóm tắt đề bài: cho một dãy $a$ gồm $N$ số và một số $p$. Bạn cần xóa đi một đoạn (liên tiếp) có độ dài ngắn nhất sao cho tổng các số trong dãy còn lại chia hết cho $p$. Lưu ý, bạn không được phép xóa toàn bộ dãy. Trả về $-1$ nếu không thể xóa được; nếu không cần xóa số nào thì trả về $0$.

Mình giải thích thêm ví dụ 2 (nums = [6,3,5,2], $p = 9$): tổng là 16, chia 9 dư 7. Thử xóa từng đoạn:

Đoạn xóa	Tổng đoạn	Tổng còn lại	Chia hết cho 9?
[6], [3], [5], [2]	6, 3, 5, 2	10, 13, 11, 14	Không
[6,3]	9	7	Không
[3,5]	8	8	Không
[5,2]	7	9	Có ⇒ đáp án 2

Để ý dòng cuối: đoạn xóa đi có tổng là 7 – đúng bằng số dư của cả dãy khi chia cho 9. Đây chính là chìa khóa của bài.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Thử mọi đoạn bằng mảng cộng dồn · O(N²) – TLECách 2Cộng dồn theo số dư + map vị trí gần nhất · O(N·logN)

Cách 1Thử mọi đoạn bằng mảng cộng dồn – O(N²)

Cách làm theo đúng đề: gọi $total$ là tổng cả dãy. Nếu $total$ chia hết cho $p$ thì trả về 0 luôn. Ngược lại, thử độ dài đoạn xóa $len$ từ nhỏ đến lớn ($1 \le len \lt N$ vì không được xóa hết), với mỗi $len$ thử mọi vị trí bắt đầu $l$. Tổng đoạn bị xóa tính trong $O(1)$ nhờ mảng cộng dồn $s$: $s[l + len] - s[l]$. Gặp đoạn nào làm $total - $ tổng đoạn chia hết cho $p$ thì đó là đáp án (vì $len$ đang tăng dần nên đoạn tìm thấy đầu tiên là ngắn nhất). Thử hết mà không có thì trả về $-1$.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int n = (int) nums.size();
        vector<long long> s(n + 1, 0);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + nums[i];
        }
        long long total = s[n];
        if (total % p == 0) {
            return 0;
        }
        for (int len = 1; len < n; len++) {
            for (int l = 0; l + len <= n; l++) {
                long long removed = s[l + len] - s[l];
                if ((total - removed) % p == 0) {
                    return len;
                }
            }
        }
        return -1;
    }
};

int main() {
    int n, p;
    cin >> n >> p;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    Solution sol;
    cout << sol.minSubarray(nums, p);
    return 0;
}

import sys
from typing import List


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)
        s = [0] * (n + 1)
        for i in range(n):
            s[i + 1] = s[i] + nums[i]
        total = s[n]
        if total % p == 0:
            return 0
        for length in range(1, n):
            for l in range(0, n - length + 1):
                removed = s[l + length] - s[l]
                if (total - removed) % p == 0:
                    return length
        return -1


def main():
    data = sys.stdin.read().split()
    n, p = int(data[0]), int(data[1])
    nums = list(map(int, data[2:2 + n]))
    print(Solution().minSubarray(nums, p))


if __name__ == "__main__":
    main()

TLE với N = 10^5

Có khoảng $\frac{N^2}{2} = 5 \cdot 10^9$ đoạn, trường hợp đáp án là $-1$ hoặc đáp án lớn là phải duyệt gần hết. Mình thử một test $N = 10^5$ ngẫu nhiên có đáp án 8401 thì code C++ đã mất khoảng 2.5 giây. Cách này chỉ dùng để hiểu đề và làm code đối chiếu. Lưu ý mảng cộng dồn phải dùng long long vì tổng có thể lên tới $10^5 \cdot 10^9 = 10^{14}$.

Không gian$O(N)$

Thời gian$O(N^2)$

Cách 2Cộng dồn theo số dư + map vị trí gần nhất – O(N·logN)

Ý tưởng giải quyết bài toán: ta gọi $r = (a[1] + a[2] + \ldots + a[n]) \bmod p$. Muốn sau khi xóa một đoạn mà tổng các phần tử còn lại chia hết cho $p$ thì đoạn ta cần xóa cũng phải có số dư là $r$ khi chia cho $p$ (như ví dụ 2 ở trên: $r = 7$, xóa đoạn $[5, 2]$ có tổng 7).

Gọi $sum[i] = a[1] + a[2] + \ldots + a[i]$ (ta chỉ cần lưu phần dư khi chia cho $p$), $sum[0] = 0$. Tổng các số trong đoạn từ $j + 1$ đến $i$ là $sum[i] - sum[j]$, số dư là $(sum[i] - sum[j] + p) \bmod p$.

Do đó, với $sum[i]$ hiện tại, một vị trí $j \lt i$ thỏa mãn là khi $(sum[i] - sum[j] + p) \bmod p = r$, tức là:

sum[j] = (sum[i] − r + p) mod p  =  needr

Đoạn xóa là $[j + 1 .. i]$ có độ dài $i - j$, nên trong các vị trí $j$ thỏa $sum[j] = needr$, ta chỉ cần chọn vị trí $j$ gần $i$ nhất (lớn nhất).

Cách làm

Gọi pos[x] là vị trí $j$ gần nhất (tính tới hiện tại) có $sum[j] \bmod p = x$, ban đầu pos[0] = 0. Duyệt $i$ từ 1 đến $n$: tính $sum$, tính $needr = (sum - r + p) \bmod p$; nếu pos[needr] tồn tại thì cập nhật ans = min(ans, i - pos[needr]); rồi ghi đè pos[sum] = i (vị trí mới luôn gần hơn vị trí cũ). Cuối cùng nếu ans = n tức là phải xóa cả dãy – không được phép – nên trả về $-1$.

Vì số $p \le 10^9$ nên pos được tổ chức bởi map chứ không thể sử dụng mảng (mảng $10^9$ phần tử thì tràn bộ nhớ).

Các bạn nhập dãy và $p$ rồi bấm Tiếp để xem từng bước (ô xanh là đoạn ngắn nhất tìm được tới thời điểm đó):

nums p

Ví dụ nhanh:

Code dưới đây của mình đã AC với tư tưởng đã trình bày ở trên, anh em có thể tham khảo nhé:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minSubarray(vector<int>& nums, int p) {
        int r = 0;
        int n = (int) nums.size();
        for (int i = 0; i < n; i++) {
            (r += nums[i]) %= p;
        }
        if (r == 0) {
            return 0;
        }
        int ans = 100005;
        map<int, int> pos;
        pos[0] = 0;
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum = (sum + nums[i - 1]) % p;
            int needr = (sum - r + p) % p;
            if (pos.find(needr) != pos.end()) {
                ans = min(ans, i - pos[needr]);
            }
            pos[sum] = i;
        }
        return (ans == n ? -1 : ans);
    }
};

int main() {
    int n, p;
    cin >> n >> p;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    Solution sol;
    cout << sol.minSubarray(nums, p);
    return 0;
}

import sys
from typing import List


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        r = 0
        n = len(nums)
        for i in range(n):
            r = (r + nums[i]) % p
        if r == 0:
            return 0
        ans = 100005
        pos = {0: 0}
        s = 0
        for i in range(1, n + 1):
            s = (s + nums[i - 1]) % p
            needr = (s - r + p) % p
            if needr in pos:
                ans = min(ans, i - pos[needr])
            pos[s] = i
        return -1 if ans == n else ans


def main():
    data = sys.stdin.read().split()
    n, p = int(data[0]), int(data[1])
    nums = list(map(int, data[2:2 + n]))
    print(Solution().minSubarray(nums, p))


if __name__ == "__main__":
    main()

Giải thích một số chỗ trong code:

1. (r += nums[i]) %= p: cộng rồi lấy dư ngay, nên r luôn nhỏ hơn $p$. Nhờ vậy dùng int vẫn an toàn: lớn nhất là $(p - 1) + 10^9 \lt 2 \cdot 10^9 \lt 2^{31} - 1$. Tương tự với sum và sum - r + p.
2. Cộng thêm p trong (sum - r + p) % p là để tránh số âm khi sum < r (trong C++ phép % với số âm cho kết quả âm).
3. ans khởi tạo bằng 100005, lớn hơn $n$ tối đa. Thực ra luôn tìm được ít nhất một đoạn: khi $i = n$ thì $sum = r$, $needr = 0$ và pos[0] luôn có (ít nhất là vị trí 0), tức là đoạn xóa cả dãy. Nên nếu không có đoạn nào ngắn hơn thì ans đúng bằng $n$ ⇒ trả về $-1$.
4. Phải kiểm tra needr trước rồi mới ghi pos[sum] = i, để không ghép $i$ với chính nó (đoạn rỗng).

Khung chạy tay (để dễ theo dõi, giới hạn $n \le 15$):

C++▶ Chạy tay từng dòng codeCách 2: duyệt sum dồn theo số dư, tra map pos để tìm vị trí j gần nhất có sum[j] = (sum - r + p) % p.

Dữ liệu vào (stdin) – sửa thoải mái4 9 6 3 5 2

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4class Solution {

5public:

6 int minSubarray(vector<int>& nums, int p) {

7 int r = 0;

8 int n = (int) nums.size();

9 for (int i = 0; i < n; i++) {

10 (r += nums[i]) %= p;

11 }

12 if (r == 0) {

13 return 0;

14 }

15 int ans = 100005;

16 map<int, int> pos;

17 pos[0] = 0;

18 int sum = 0;

19 for (int i = 1; i <= n; i++) {

20 sum = (sum + nums[i - 1]) % p;

21 int needr = (sum - r + p) % p;

22 if (pos.find(needr) != pos.end()) {

23 ans = min(ans, i - pos[needr]);

24 }

25 pos[sum] = i;

26 }

27 return (ans == n ? -1 : ans);

28 }

29};

30

31int main() {

32 int n, p;

33 cin >> n >> p;

34 vector<int> nums(n);

35 for (int i = 0; i < n; i++) cin >> nums[i];

36 Solution sol;

37 cout << sol.minSubarray(nums, p);

38 return 0;

39}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: map pos có tối đa $\min(n + 1, p)$ khóa – $O(N)$.
• Thời gian: mỗi vị trí làm một lần tìm và một lần ghi trên map, mỗi thao tác $O(\log N)$ ⇒ $O(N \log N)$.

Không gian$O(N)$

Thời gian$O(N \log N)$

Mở rộng

Thay map bằng unordered_map (C++) thì độ phức tạp trung bình là $O(N)$. Bản Python ở trên dùng dict nên đã là $O(N)$ trung bình rồi.

Ghi chú của mình: Code C++ và Python của cả 2 cách đã được kiểm tra với 5 ví dụ của đề (đều đúng) và 500 bộ test ngẫu nhiên ($n \le 12$, $p$ nhỏ lẫn $p$ tới $10^9$, $nums[i]$ tới $10^9$, có cả các test đáp án $-1$), so với code vét cạn thử mọi đoạn – khớp hết. Với $n = 10^5$, Cách 2 C++ chạy khoảng 0.1 giây, Python khoảng 0.1 giây; còn Cách 1 C++ mất khoảng 2.5 giây ở test có đáp án 8401 và sẽ chậm hơn nữa nếu đáp án là $-1$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇