Các mảng con là phần liền kề của một mảng. Ví dụ, chúng ta xem xét một mảng [5, 6, 7, 8], sau đó có mười mảng con không rỗng như (5), (6), (7), (8), (5, 6), (6 , 7), (7,8), (5,6,7), (6,7,8) và (5,6,7,8).
Trong hướng dẫn này, chúng tôi sẽ giải thích mọi thông tin có thể có để tìm số lượng mảng con có tổng số lẻ trong C ++. Để tìm số lượng các mảng con có tổng lẻ, chúng ta có thể sử dụng các cách tiếp cận khác nhau, vì vậy đây là một ví dụ đơn giản cho nó -
Input : array = {9,8,7,6,5}
Output : 9
Explanation :
Sum of subarray -
{9} = 9
{7} = 7
{5} = 5
{9,8} = 17
{8,7} = 15
{7,6} = 13
{6,5} = 11
{8,7,6} = 21
{9,8,7,6,5} = 35 Phương pháp tiếp cận vũ phu
Với cách tiếp cận này, chúng ta có thể đơn giản kiểm tra xem tổng các phần tử trong tất cả các mảng con là chẵn hay lẻ, Nếu nó là chẵn, chúng ta sẽ từ chối mảng con đó và sẽ đếm các mảng con có tổng số lẻ, Đây không phải là một cách tiếp cận hiệu quả vì độ phức tạp của mã này là O (n 2 ).
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int n=5, temp = 0;
int a[n-1] = { 9,8,7,6,5 } ; // declaring our array.
int cnt = 0; // counter variable.
for(int i = 0; i < n; i++){
temp = 0; // refreshing our temp sum.
for(int j = i; j < n; j++){ // this loop will make our subarrays starting from i till n-1.
temp = temp + a[j];
if( temp % 2 == 1 )
cnt++;
}
}
cout << "Number of subarrays with odd sum : " << cnt << "\n";
return 0;
} Đầu ra
Number of subarrays with odd sum : 9
Giải thích về Quy tắc trên
Các vòng lặp lồng nhau được sử dụng trong đoạn mã này, trong đó vòng lặp bên ngoài được sử dụng để tăng giá trị của I, giá trị này đang trỏ vào mỗi giá trị của mảng kể từ khi bắt đầu; vòng lặp bên trong được sử dụng để tìm mảng con bắt đầu từ vị trí "i" có tổng số lẻ.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi đang xử lý mọi phần tử từ vị trí thứ 0 trong mảng. Nếu phần tử hiện tại là số lẻ, hãy tăng một bộ đếm lẻ và tăng một bộ đếm chẵn cho mọi số chẵn. Nếu chúng ta tìm thấy một số lẻ, thì hãy hoán đổi các giá trị của chẵn và lẻ vì thêm một số lẻ vào mảng con sẽ thay đổi tính chẵn lẻ của nó và cuối cùng là thêm một số đếm vào kết quả. Độ phức tạp của mã này là O (n), vì chúng tôi đang xử lý mọi phần tử.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int main(){
int odd = 0, even = 0, result = 0,n=5,i,temp;
int arr[ n-1 ] = { 9,8,7,6,5}; // initialising the array
// for loop for processing every element of array
for ( i = 0 ; i < n ; i ++ ) {
if ( arr[ i ] % 2 == 0 ) {
even++;
} else {
// swapping even odd values
temp = even;
even = odd;
odd = temp + 1;
}
result += odd;
}
cout << "Number of subarrays with odd sum : " << result;
} Đầu ra
Number of subarrays with odd sum : 9
Giải thích về Quy tắc trên
Trong mã này, chúng tôi kiểm tra mọi phần tử cho bộ đếm chẵn / lẻ và bộ đếm chẵn tăng dần cho số chẵn và bộ đếm lẻ cho một số lẻ. Ngoài ra, chúng tôi đang hoán đổi các giá trị bộ đếm chẵn lẻ nếu một số lẻ được tìm thấy; nếu không, nó sẽ thay đổi tính chẵn lẻ của mảng con. Sau đó, thêm giá trị của bộ đếm lẻ vào biến kết quả sau mỗi lần lặp.
Kết luận
Trong bài viết này, chúng tôi đã giải thích cách tìm số lượng mảng con có tổng số lẻ từ phương pháp Brute force, phương pháp này đang tạo ra mọi mảng con có tổng số lẻ và tăng số lượng. Độ phức tạp về thời gian của mã này là O (n2). Một cách tiếp cận hiệu quả là đi qua từng phần tử của mảng và tăng dần các biến bộ đếm chẵn / lẻ với mọi số lẻ / chẵn được tìm thấy và hoán đổi bộ đếm nếu tìm thấy số lẻ; độ phức tạp về thời gian của mã này là O (n). Hy vọng bạn thấy bài viết này hữu ích trong việc hiểu vấn đề và giải pháp.