Concatenation of Consecutive Binary Numbers (LeetCode 1680)

Nguồn: LeetCode 1680 Độ khó: Trung bình (Medium) Xử lý bit Modulo Toán học

Đề bài

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

1680. Concatenation of Consecutive Binary Numbers – Ghép các số nhị phân liên tiếp (LeetCode, độ khó Medium)

Cho một số nguyên $n$, hãy trả về giá trị thập phân của xâu nhị phân tạo thành khi ghép nối lần lượt biểu diễn nhị phân của các số từ $1$ đến $n$ theo thứ tự, lấy phần dư khi chia cho $10^9 + 7$.

Ràng buộc:

• $1 \le n \le 10^5$

Đị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 concatenatedBinary 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: một dòng duy nhất chứa số nguyên $n$.
• Kết quả: một số nguyên là đáp án của bài.

Ví dụ 1

Input: n = 1
Output: 1
---stdin---
1

Xâu "1" ở hệ nhị phân ứng với giá trị thập phân là 1.

Ví dụ 2

Input: n = 3
Output: 27
---stdin---
3

Ở hệ nhị phân, 1, 2 và 3 lần lượt là "1", "10" và "11". Ghép lại ta được "11011", ứng với giá trị thập phân 27.

Ví dụ 3

Input: n = 12
Output: 505379714
---stdin---
12

Xâu ghép được là "1101110010111011110001001101010111100", có giá trị thập phân 118505380540. Lấy dư cho $10^9 + 7$ được 505379714.

1680. Concatenation of Consecutive Binary Numbers (LeetCode, Medium)

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 10^9 + 7, the result is 505379714.

Constraints:

• 1 <= n <= 10^5

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.

Giải thích ví dụ 2 cho bạn nào chưa hiểu đề: viết các số $1, 2, 3$ ra hệ nhị phân rồi đặt sát nhau:

Số	1	2	3	Ghép lại
Nhị phân	1	10	11	11011

$11011_2 = 16 + 8 + 0 + 2 + 1 = 27$. Với $n = 12$ xâu ghép đã dài 37 bit, giá trị hơn $10^{11}$; còn $n = 10^5$ thì xâu dài cả triệu bit – không kiểu số nào chứa nổi, nên đề mới bắt lấy dư cho $10^9 + 7$.

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

Cách 1Đổi nhị phân → thập phân theo từng bit · O(N·logN)Cách 2Dịch trái cả cụm bit một lần · O(N)

Cách 1Đổi nhị phân sang thập phân theo từng bit – O(N·logN)

Phương pháp giải: Duyệt.

Lý thuyết: đổi một số nhị phân sang thập phân có thể làm như sau. Gọi $ans$ là kết quả thập phân, ban đầu $ans = 0$. Duyệt các bit từ vị trí cao nhất đến vị trí thấp nhất:

• nếu bit đó bằng 1 thì $ans = ans \cdot 2 + 1$;
• nếu bit đó bằng 0 thì $ans = ans \cdot 2$.

Ví dụ $1011_2$: $0 \to 1 \to 2 \to 5 \to 11$. Đúng là $1011_2 = 11$.

Ý chính

Xâu cần đổi chính là các bit của số 1, rồi các bit của số 2, …, rồi các bit của số $n$ đặt nối tiếp nhau. Vậy ta cứ đổi nhị phân sang thập phân đúng như lý thuyết trên, chỉ có điều lần này là đi qua các bit của từng số $i = 1, 2, \ldots, n$ lần lượt. Với mỗi số $i$, duyệt từ bit 1 cao nhất của $i$ xuống bit 0: bit bằng 1 thì $ans = ans \cdot 2 + 1$, bit bằng 0 thì $ans = ans \cdot 2$. Sau mỗi phép tính lấy dư cho $10^9 + 7$ là xong.

Vì sao được phép lấy dư ngay sau mỗi bước? Vì ta chỉ dùng phép nhân và phép cộng, mà $(a \cdot 2 + b) \bmod M = ((a \bmod M) \cdot 2 + b) \bmod M$. Nhờ đó $ans$ luôn nhỏ hơn $10^9 + 7$, nhân 2 vẫn nằm gọn trong long long.

Để tìm vị trí bit 1 cao nhất của $i$ (gọi là maxBit), mình duyệt $j$ từ 18 xuống 0, gặp bit 1 đầu tiên thì dừng. Vì $n \le 10^5 \lt 2^{17}$ nên bắt đầu từ bit 18 là dư sức.

Các bạn nhập $n$ rồi bấm Tiếp để xem từng bit được "nạp" vào $ans$ (ô vàng là bit đang xét, ô xanh là bit đã nạp):

n

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;

const long long MOD = 1000000007;
class Solution {
public:
    int concatenatedBinary(int n) {
        long long ans = 0LL;
        for (int i = 1; i <= n; i++) {
            int maxBit = 0;
            for (int j = 18; j >= 0; j--) {
                if ((i & (1 << j)) > 0) {
                    maxBit = j;
                    break;
                }
            }
            for (int j = maxBit; j >= 0; j--) {
                (ans *= 2LL) %= MOD;
                if ((i & (1 << j)) > 0) {
                    ans++;
                    ans %= MOD;
                }
            }
        }
        return (int) ans;
    }
};

int main() {
    int n;
    cin >> n;
    Solution sol;
    cout << sol.concatenatedBinary(n);
    return 0;
}

MOD = 1000000007


class Solution:
    def concatenatedBinary(self, n: int) -> int:
        ans = 0
        for i in range(1, n + 1):
            max_bit = 0
            for j in range(18, -1, -1):
                if (i >> j) & 1:
                    max_bit = j
                    break
            for j in range(max_bit, -1, -1):
                ans = ans * 2 % MOD
                if (i >> j) & 1:
                    ans = (ans + 1) % MOD
        return ans


def main():
    n = int(input())
    print(Solution().concatenatedBinary(n))


if __name__ == "__main__":
    main()

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

1. (i & (1 << j)) > 0: kiểm tra bit thứ $j$ của $i$ có bằng 1 không (1 << j là số chỉ có đúng bit $j$ bật).
2. (ans *= 2LL) %= MOD: nhân đôi rồi lấy dư ngay. Nếu bit bằng 1 thì cộng thêm 1 và lấy dư lần nữa.
3. ans khai báo long long để ans * 2 (có thể gần $2 \cdot 10^9$) không bị tràn int.

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

C++▶ Chạy tay từng dòng codeCách 1: với mỗi i tìm bit cao nhất, rồi nạp từng bit vào ans = ans * 2 (+1).

Dữ liệu vào (stdin) – sửa thoải mái3

Dữ liệu mẫu:

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

2using namespace std;

3

4const long long MOD = 1000000007;

5class Solution {

6public:

7 int concatenatedBinary(int n) {

8 long long ans = 0LL;

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

10 int maxBit = 0;

11 for (int j = 18; j >= 0; j--) {

12 if ((i & (1 << j)) > 0) {

13 maxBit = j;

14 break;

15 }

16 }

17 for (int j = maxBit; j >= 0; j--) {

18 (ans *= 2LL) %= MOD;

19 if ((i & (1 << j)) > 0) {

20 ans++;

21 ans %= MOD;

22 }

23 }

24 }

25 return (int) ans;

26 }

27};

28

29int main() {

30 int n;

31 cin >> n;

32 Solution sol;

33 cout << sol.concatenatedBinary(n);

34 return 0;

35}

ChậmVừaNhanhRất nhanh

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

• Không gian: chỉ dùng vài biến – $O(1)$.
• Thời gian: mỗi số $i$ tốn tối đa 19 lần tìm maxBit và $\lfloor \log_2 i \rfloor + 1$ lần nạp bit ⇒ $O(N \log N)$. Với $n = 10^5$ chỉ khoảng $3 \cdot 10^6$ phép tính.

Không gian$O(1)$

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

Cách 2Dịch trái cả cụm bit một lần – O(N)

Đây là một cải tiến nhỏ từ Cách 1 cho bạn nào thích code gọn. Nạp lần lượt $L$ bit của số $i$ vào $ans$ (mỗi lần nhân 2 rồi cộng bit) thì kết quả chung cuộc cũng chính là dịch $ans$ sang trái $L$ bit rồi cộng $i$:

ans = (ans · 2^L + i) mod (10⁹ + 7),   L = số bit của i

Số bit $L$ của $i$ chỉ tăng thêm 1 mỗi khi $i$ là lũy thừa của 2 ($1, 2, 4, 8, \ldots$), và $i$ là lũy thừa của 2 khi và chỉ khi (i & (i - 1)) == 0. Vì $ans \lt 10^9 + 7 \lt 2^{30}$ và $L \le 17$ nên ans << L nhỏ hơn $2^{47}$, nằm gọn trong long long; lại vì $i \lt 2^L$ nên các bit thấp của ans << L toàn 0, cộng $i$ hay OR với $i$ đều như nhau.

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

const long long MOD = 1000000007;
class Solution {
public:
    int concatenatedBinary(int n) {
        int len = 0;
        long long ans = 0LL;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                len++;
            }
            ans = ((ans << len) | i) % MOD;
        }
        return (int) ans;
    }
};

int main() {
    int n;
    cin >> n;
    Solution sol;
    cout << sol.concatenatedBinary(n);
    return 0;
}

MOD = 1000000007


class Solution:
    def concatenatedBinary(self, n: int) -> int:
        length = 0
        ans = 0
        for i in range(1, n + 1):
            if i & (i - 1) == 0:
                length += 1
            ans = ((ans << length) | i) % MOD
        return ans


def main():
    n = int(input())
    print(Solution().concatenatedBinary(n))


if __name__ == "__main__":
    main()

Không gian$O(1)$

Thời gian$O(N)$

Ghi chú của mình: Code C++ và Python của cả 2 cách đã được kiểm tra với 3 ví dụ của đề (đều đúng) và với mọi $n$ từ 1 đến 400 cùng các giá trị đặc biệt $1023, 1024, 1025, 4096, 65535, 65536, 99999, 10^5$, so với code vét cạn ghép hẳn xâu nhị phân rồi đổi bằng số nguyên lớn của Python – khớp hết. Với $n = 10^5$, Cách 1 C++ chạy khoảng 0.01 giây, Python khoảng 0.3 giây; Cách 2 Python khoảng 0.05 giây.

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 😇