Đếm các mảng con có các phần tử liên tiếp khác nhau 1 trong C ++

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