Chúng ta được cung cấp một mảng arr [] chứa các số nguyên. Mục đích là đếm tất cả các mảng con của arr [] sao cho các phần tử liên tiếp trong mỗi mảng con chỉ khác nhau 1. Nếu mảng là [1,2,3] .Subarrays sẽ chỉ là [1,2], [2,3], [1,2,3].
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - arr [] ={4,3,2,1};
Đầu ra - Số lượng Mảng con có các phần tử Liên tiếp chênh lệch nhau 1 là - 6
Giải thích - Các nhóm phụ sẽ -
[4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1]. Total 6.
Đầu vào - arr [] ={1,5,6,7,9,11};
Đầu ra - Số lượng Mảng con có các phần tử Liên tiếp chênh lệch nhau 1 là - 3
Giải thích - Các nhóm phụ sẽ -
[5,6], [6,7], [5,6,7]. Total 3
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Chúng ta sẽ duyệt qua mảng bằng vòng lặp for. Từ i =0 đến i
-
Lấy một mảng [] số.
-
Hàm sub_ele_diff_one (int arr [], int size) nhận mảng và trả về số lượng các mảng con với các phần tử liên tiếp khác nhau bằng 1.
-
Lấy số lượng ban đầu là 0.
-
Chúng tôi sẽ duyệt qua mảng bằng cách sử dụng vòng lặp for từ i =0 đến I
-
Lấy hai biến đầu tiên, cuối cùng là 0 cho các chỉ mục mà tất cả các phần tử đều liên tiếp và khác nhau bằng 1.
-
Kiểm tra xem arr [i-1] -arr [i] ==1 HOẶC arr [i] -arr [i-1] ==1. (các phần tử khác nhau 1). Nếu đúng, hãy tăng trước.
-
Nếu điều kiện trước đó là false, thì tổng các phần tử trong mảng thỏa mãn điều kiện này là temp =first-last + 1. Các mảng con có thể có là tổng =temp * (temp-1) / 2.
-
Bây giờ, hãy thêm tổng số mảng con này để đếm.
-
Cập nhật chỉ mục đầu tiên và cuối cùng với I hiện tại (chỉ mục mà tại đó điều kiện phần tử liên tiếp không thành công.
-
Ở cuối vòng lặp for if first! =Last. Điều này có nghĩa là mảng còn lại thỏa mãn điều kiện. Áp dụng các bước tương tự và cộng tổng số để đếm.
-
Ở cuối cả hai vòng, kết quả trả về là số lượng.
Ví dụ
#include <iostream> using namespace std; int sub_ele_diff_one(int arr[], int size){ int count = 0, first = 0, last = 0; for (int i = 1; i < size; i++){ if (arr[i] - arr[i - 1] == 1 || arr[i-1] - arr[i] == 1){ first++; } else{ int temp = first - last + 1; int total = temp * (temp - 1) / 2; count = count + total; first = i; last = i; } } if (first != last){ int temp = first - last + 1; int total = temp * (temp - 1) / 2; count = count + total; } return count; } int main(){ int arr[] = { 1, 2, 4, 3 }; int size = sizeof(arr) / sizeof(arr[0]); cout<<"Count of Subarrays with Consecutive elements differing by 1 are: "<<sub_ele_diff_one(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 -
Count of Subarrays with Consecutive elements differing by 1 are: 2