Số lượng phần tử mảng liên tiếp tối đa có cùng số bit set trong C++

Chúng ta được cung cấp một mảng các số nguyên không được sắp xếp và nhiệm vụ là tính hai điều chính:

• Các phần tử có cùng số bit set (bit 1).
• Các phần tử có cùng số bit set phải là liên tiếp nhau.

Ví dụ

Đầu vào

int arr[] = { 5, 8, 1, 2, 9, 12}

Đầu ra − Số lượng phần tử mảng liên tiếp tối đa có cùng số bit set là − 3

Giải thích − Chúng ta sẽ tính dạng nhị phân của các phần tử mảng và đếm số bit set của chúng.

arr[0] = 5 => 0101 => tổng bit set là: 2
arr[1] = 8 => 1000 => tổng bit set là: 1
arr[2] = 1 => 0001 => tổng bit set là: 1
arr[3] = 2 => 0010 => tổng bit set là: 1
arr[4] = 9 => 1001 => tổng bit set là: 2
arr[5] = 12 => 1100 => tổng bit set là: 2

Vì vậy, các phần tử có cùng số bit set và cũng liên tiếp nhau là 5, 9 và 12. Do đó, số lượng phần tử mảng liên tiếp tối đa có cùng số bit set là 3.

Đầu vào − int arr[] = { 5, 8, 1, 2}

Đầu ra − Số lượng phần tử mảng liên tiếp tối đa có cùng số bit set là − 2

Giải thích − Các phần tử có cùng số bit set và liên tiếp là 1 và 2. Do đó, kết quả là 2.

Phương pháp sử dụng trong chương trình dưới đây

• Nhập các phần tử mảng kiểu số nguyên.
• Tính kích thước mảng bằng hàm size và truyền cho hàm xử lý.
• Tạo biến tạm temp gán giá trị 1 và biến maximum gán giá trị 1.
• Tạo biến vec kiểu vector.
• Vòng lặp for từ 0 đến kích thước mảng.
• Tính số bit set của các phần tử mảng bằng hàm "__builtin_popcount(element)" trả về tổng số bit set của phần tử được truyền vào và lưu số lượng vào vector.
• Vòng lặp for từ 1 đến kích thước vector.
• Trong vector, kiểm tra nếu vec[i+1] == vec[i] thì tăng temp lên 1.
• Ngược lại, gán temp = 1.
• Gán maximum bằng giá trị max giữa temp và maximum bằng hàm max.
• Trả về biến maximum.
• In kết quả.

Ví dụ mã nguồn

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

// Hàm tính số lượng phần tử liên tiếp có cùng số bit set tối đa
int maximum_SameBits(int arr[], int size) { 
    int temp = 1; 
    int maximum = 1; 
    vector<int> vec; 
    for (int i = 0; i < size; i++) { 
        vec.push_back(__builtin_popcount(arr[i])); 
    } 
    for (int i = 1; i < vec.size(); i++) { 
        if (vec[i + 1] == vec[i]) { 
            temp++; 
        } else { 
            temp = 1; 
        } 
        maximum = max(maximum, temp); 
    } 
    return maximum; 
} 

int main() { 
    int arr[] = { 5, 8, 1, 2, 9, 12}; 
    int size = sizeof(arr) / sizeof(arr[0]); 
    cout << "Số lượng phần tử mảng liên tiếp tối đa có cùng số bit set: " 
         << maximum_SameBits(arr, size); 
    return 0; 
}

Kết quả

Số lượng phần tử mảng liên tiếp tối đa có cùng số bit set: 3