Chúng ta được cung cấp một mảng các số nguyên dương. Mục đích là tìm các mảng con của các số trong một mảng sao cho mỗi mảng con có cùng số phần tử chẵn và lẻ trong đó. Nếu mảng là {1,2,3,4}. Khi đó, các mảng con sẽ là {1,2}, {2,3}, {3,4}, {1,2,3,4}. Tổng số mảng con như vậy là 4.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,3,5,7,8,3,2};
Đầu ra - Số lượng các mảng con có cùng phần tử chẵn và lẻ là - 4
Giải thích - Các mảng con sẽ là - {7,8}, {8,3} {3,2}, {7,8,3,2}
Đầu vào - arr [] ={2,4,6};
Đầu ra - Số lượng các mảng con có cùng phần tử chẵn và lẻ là - 0
Giải thích - Tất cả các yếu tố đều.
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng ta sẽ sử dụng một biến temp làm hiệu giữa các phần tử của mảng (ban đầu là 0) và tăng nó lên 1 nếu arr [i] là lẻ và giảm nó đi 1 nếu arr [i] là chẵn. Khi giá trị của temp lặp lại chính nó thì phải tồn tại một mảng con có cùng số chẵn-lẻ giữa các chỉ mục này. Nhiệt độ có thể tích cực cũng như tiêu cực. Lấy hai mảng băm arr_1 [size + 1] cho tần suất chênh lệch dương và arr_2 [size + 1] cho tần suất chênh lệch âm.
Đối với mỗi chênh lệch nhiệt độ <0, hãy thêm tần số từ arr_1 [-temp] để đếm. [- (- temp)] cho một chỉ số dương.
Đối với mỗi chênh lệch nhiệt độ> 0, hãy thêm tần số từ arr_2 [temp] để đếm. Vì tất cả các lần xuất hiện có cùng giá trị chênh lệch sẽ là một phần của các mảng con. Cập nhật các tần số này bằng 1.
Arr[] = { 1,3,5,7,8,3,2 } Giá trị nhiệt độ bắt đầu từ 0 -
1,2,3,4,3,4,3
arr_1[] { 1,1,1,3,2,0,0,0 } //all differences are positive
arr_2[] { 0,0,0,0,0,0,0,0 } //no difference is negative
Adding arr_1[temp] to count in each iteration gives count=4. Các mảng con là - {7,8}, {8,3} {3,2}, {7,8,3,2}
-
Lấy mảng ban đầu là arr [].
-
Hàm Sub_even_odd (int arr [], int size) nhận mảng và độ dài của nó và trả về số lượng các mảng con có cùng phần tử chẵn và lẻ.
-
Lấy tổng số ban đầu là 0 và biến temp làm biến tăng khi gặp giá trị lẻ và giảm khi gặp giá trị chẵn.
-
Lấy hai mảng arr_1 [] và arr_2 [] để lưu trữ tần số tạm thời. arr_1 [] cho các giá trị dương của nhiệt độ có thể lên đến kích thước + 1 trong trường hợp toàn bộ mảng là số chẵn.
arr_2 [] cho các giá trị âm của nhiệt độ có thể lên đến kích thước + 1 trong trường hợp toàn bộ mảng là số chẵn.
-
Traverse arr [] bằng vòng lặp for.
-
Nếu arr [i] &1 ==1 có nghĩa là arr [i] là số lẻ. Tăng nhiệt độ. Nhiệt độ giảm khác.
-
Nếu nhiệt độ <0 thì thêm tần số tương ứng từ arr_2 [] để đếm. Tăng tần suất đó lên 1.
-
Nếu nhiệt độ> 0 thì thêm tần số tương ứng từ arr_1 [] để đếm. Tăng tần suất đó lên 1.
-
Cuối cùng, chúng tôi đã tính là số lượng mảng con trong arr [] có cùng số phần tử chẵn và lẻ trong chúng
-
Kết quả là số lượt trả lại.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int Sub_even_odd(int arr[], int size){
int count = 0;
int temp = 0;
int arr_1[size + 1] = {0};
int arr_2[size + 1] = {0};
arr_1[0] = 1;
for (int i = 0; i < size; i++){
if(arr[i] & 1 == 1)
{ temp++; }
else
{ temp--; }
if (temp < 0){
count += arr_2[-temp];
arr_2[-temp]++;
}
else{
count += arr_1[temp];
arr_1[temp]++;
}
}
return count;
}
int main(){
int arr[] = {3, 4, 6, 1, 2, 4, 10, 42};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of subarrays with same even and odd elements are: "<<Sub_even_odd(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 same even and odd elements are: 4