Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

Cho một mảng có kích thước N, mảng chứa tất cả các số từ 1 đến N+1, ngoại trừ một số…

  1. User

    Cho một mảng có kích thước N, mảng chứa tất cả các số từ 1 đến N+1, ngoại trừ một số không có mặt. Bạn cần tìm ra số này. giải bài này bằng c++ dùng thuật toán bits

  2. Assistant

    Để giải bài toán này, ta có thể sử dụng thuật toán bits (bit manipulation).

    Cách làm như sau:

    1. Tạo một biến missingNum và gán giá trị ban đầu là 0.
    2. Duyệt qua từng phần tử trong mảng:
      • Cộng giá trị của phần tử với missingNum.
      • Sau đó, xor kết quả với số hiện tại (vì xor của hai số giống nhau sẽ trở thành 0).
    3. Vì mảng chứa tất cả các số từ 1 đến N+1, nên missingNum sẽ là số bị thiếu.

    Dưới đây là code C++ thực hiện công việc trên:

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int findMissingNumber(vector<int>& nums) {
        int missingNum = 0;
        
        for (int i = 1; i <= nums.size() + 1; i++) {
            missingNum ^= i;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            missingNum ^= nums[i];
        }
        
        return missingNum;
    }
    
    int main() {
        int n;
        cout << "Nhap so luong phan tu trong mang: ";
        cin >> n;
        
        vector<int> nums(n);
        cout << "Nhap cac phan tu trong mang: ";
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        
        int missingNumber = findMissingNumber(nums);
        
        cout << "So bi thieu la: " << missingNumber << endl;
        
        return 0;
    }
    

    Với đầu vào là một mảng có kích thước N và chứa các số từ 1 đến N+1 trừ một số không có mặt, sau khi chạy chương trình trên, sẽ hiển thị ra số bị thiếu trong mảng.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.