Đếm số bit 1 trong mảng sau N bước trong C

Cho mảng kích thước N, ban đầu toàn 0. Nhiệm vụ đếm số 1 sau N bước. Mỗi bước N có quy tắc:

• Bước 1 - Thay đổi phần tử vị trí 1, 2, 3, 4...

• Bước 2 - Thay đổi vị trí 2, 4, 6, 8...

• Bước 3 - Thay đổi vị trí 3, 6, 9, 12...

Đếm số 1 trong mảng cuối cùng.

Hiểu qua ví dụ.

Đầu vào

Arr[] = {0,0,0,0} N=4

Đầu ra

Số 1 trong mảng sau N bước: 2

Giải thích - Mảng sau các bước:

Bước 1: {1,1,1,1}
Bước 2: {1,0,1,0}
Bước 3: {1,0,0,1}
Bước 4: {1,0,0,1}
Số 1 trong mảng cuối = 2.

Đầu vào

Arr[] = {0,0,0,0,0,0} N=6

Đầu ra

Số 1 trong mảng sau N bước: 2

Giải thích - Mảng sau các bước:

Bước 1: {1,1,1,1,1,1}
Bước 2: {1,0,1,0,1,0}
Bước 3: {1,0,0,1,0,0}
Bước 4: {1,0,0,0,1,0}
Bước 5: {1,0,0,0,0,1}
Bước 6: {1,0,0,0,0,0}
Số 1 trong mảng cuối = 1 (Lưu ý: ví dụ gốc có lỗi in, kết quả thực tế là 1).

Phương pháp chương trình

• Mảng nguyên Arr[] khởi tạo 0 và số nguyên N.

• Hàm Onecount nhận Arr[] và size N trả về số 1 cuối cùng.

• Vòng lặp ngoài từ 1 đến N.

• Mỗi i đại diện bước thứ i.

• Vòng lặp trong từ 0 đến N-1.

• Với bước i, nếu chỉ số j chia hết cho i (j%i==0), đảo bit tại vị trí đó (0->1, 1->0).

• Lưu ý: chỉ số mảng từ 0, nhưng bước từ 1, nên dùng arr[j-1].

• Cuối duyệt mảng đếm số 1 lưu vào count.

• Trả về count.

Ví dụ

#include <stdio.h>
int Onecount(int arr[], int N) {
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            if (j % i == 0) {
                if (arr[j - 1] == 0)
                    arr[j - 1] = 1;
                else
                    arr[j - 1] = 0;
            }
        }
    }
    int count = 0;
    for (int i = 0; i < N; i++)
        if (arr[i] == 1)
            count++;
    return count;
}
int main() {
    int size = 6;
    int Arr[6] = {0};
    printf("So 1 trong mang sau N buoc: %d", Onecount(Arr, size));
    return 0;
}

Kết quả

Chạy code cho đầu ra:

So 1 trong mang sau N buoc: 2