Chúng ta được cung cấp một mảng có kích thước N. Ban đầu mảng có tất cả các số 0. Nhiệm vụ là đếm số không. của 1 trong mảng sau khi N di chuyển. Mỗi nước đi thứ N có một quy tắc liên quan. Các quy tắc là -
-
Nước đi thứ nhất - Thay đổi phần tử ở các vị trí 1, 2, 3, 4 ………… ..
-
Nước đi thứ 2 - Thay đổi phần tử ở các vị trí 2, 4, 6, 8 ………… ..
-
Nước đi thứ 3 - Thay đổi phần tử ở các vị trí 3, 6, 9, 12 ………… ..
Đếm số 1 trong mảng cuối cùng.
Hãy cùng hiểu với các ví dụ.
Đầu vào
Arr[]={ 0,0,0,0 } N=4 Đầu ra
Number of 1s in the array after N moves − 2
Giải thích - Mảng sau khi di chuyển sau -
Move 1: { 1,1,1,1 }
Move 2: { 1,0,1,0 }
Move 3: { 1,0,0,3 }
Move 4: { 1,0,0,1 }
Number of ones in the final array is 2. Đầu vào
Arr[]={ 0,0,0,0,0,0} N=6 Đầu ra
Number of 1s in the array after N moves − 2
Giải thích - Mảng sau khi di chuyển sau -
Move 1: { 1,1,1,1,1,1,1 }
Move 2: { 1,0,1,0,1,0,1 }
Move 3: { 1,0,0,1,0,0,1 }
Move 4: { 1,0,0,0,1,0,0 }
Move 5: { 1,0,0,0,0,1,0 }
Move 4: { 1,0,0,0,0,0,1 }
Number of ones in the final array is 2. Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Chúng tôi lấy một mảng số nguyên Arr [] được khởi tạo với số nguyên 0 và N.
-
Hàm Onecount lấy Arr [] và nó có kích thước N làm đầu vào và trả về không. những cái trong mảng cuối cùng sau khi N di chuyển.
-
Vòng lặp for bắt đầu từ 1 cho đến cuối mảng.
-
Mỗi tôi đại diện cho nước đi thứ i.
-
Vòng lặp for lồng nhau bắt đầu từ chỉ mục thứ 0 cho đến cuối mảng.
-
Đối với mỗi lần di chuyển thứ i, nếu chỉ số j là bội số của i (j% i ==0), hãy thay thế 0 bằng 1 tại vị trí đó.
-
Quá trình này tiếp tục cho từng i cho đến khi kết thúc mảng.
-
Lưu ý - Chỉ mục bắt đầu từ i =1, j =1 nhưng chỉ số mảng từ 0 đến N-1. Vì lý do này, arr [j1] được chuyển đổi mỗi lần.
-
Cuối cùng duyệt lại toàn bộ mảng và đếm không. của 1 trong số đó và lưu trữ vào số lượng.
- Số lượt trả về là kết quả mong muốn.
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 is divisible by i
if (j % i == 0) {
if (arr[j - 1] == 0)
arr[j - 1] = 1; // Convert 0 to 1
else
arr[j - 1] = 0; // Convert 1 to 0
}
}
}
int count = 0;
for (int i = 0; i < N; i++)
if (arr[i] == 1)
count++; // count number of 1's
return count;
}
int main(){
int size = 6;
int Arr[6] = { 0 };
printf("Number of 1s in the array after N moves: %d", Onecount(Arr, size));
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Number of 1s in the array after N moves: 2