Chúng ta được cung cấp với một mảng arr [] gồm N phần tử. Mục đích là tìm số lượng tất cả các cặp chỉ số hợp lệ (i, j) sao cho arr [i] chia hết cho arr [j] hoặc arr [j] chia hết cho arr [i] và i! =J.
Chúng tôi sẽ thực hiện việc này bằng cách duyệt qua mảng arr [] sử dụng hai vòng lặp for cho mỗi số cặp và kiểm tra xem arr [i]% arr [j] ==0 hay arr [j]% arr [i] ==0 khi tôi ! =j. Nếu số lượng cặp gia tăng đúng.
Hãy cùng hiểu với các ví dụ.
Đầu vào - Arr [] ={2,4,3,6} N =4
Đầu ra - Số lượng các cặp hợp lệ - 3
Giải thích - Các cặp hợp lệ là -
Arr[0] & Arr[1] → (2,4) here 4%2==0 0!=1 Arr[0] & Arr[1] → (2,6) here 6%2==0 0!=3 Arr[2] & Arr[3] → (3,6) here 6%3==0 2!=3
Đầu vào - Arr [] ={2,5,7,9,11} N =5
Đầu ra - Số lượng các cặp hợp lệ - 0
Giải thích - Không có số nào chia hết cho số kia. Không có cặp nào có thể được tạo thành.
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 các số ngẫu nhiên.
-
Lấy một biến n lưu trữ độ dài của Arr [].
-
Hàm countPairs (int arr [], int n) nhận một mảng, độ dài của nó làm đầu vào và trả về các cặp hợp lệ và đáp ứng các điều kiện mong muốn.
-
Traverse mảng sử dụng hai vòng lặp for cho mỗi phần tử của cặp.
-
Vòng ngoài từ 0 <=i
-
Kiểm tra xem arr [i]% arr [j] ==0 hay arr [j]% arr [i] ==0. Số lượng tăng lên một lần nếu một trong hai điều kiện là nguyên.
-
Ở cuối tất cả các vòng đếm sẽ có tổng số cặp hợp lệ
-
Trả về kết quả là số lượng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int countPairs(int arr[], int n){
// Count of pairs
int count = 0;
for (int i = 0; i < n-1; i++){
for (int j = i + 1; j < n; j++){
if(arr[i]%arr[j]==0 || arr[j]%arr[i]==0)
{ count++; }
}
}
return count;
}
int main(){
int Arr[] = { 2,3,4,5,6 };
int len = sizeof(Arr) / sizeof(Arr[0]);
cout << "Count of number of pairs : "<< countPairs(Arr, len);
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 -
Count of number of pairs : 3