Write a code using C++ to find the number of subarrays with the same minimum and maximum values

In this article, we will use C to solve the problem of finding the number of subarrays with the same maximum and minimum values. Following is an example of this problem −

Input : array = { 2, 3, 6, 6, 2, 4, 4, 4 }
Output : 12
Explanation : {2}, {3}, {6}, {6}, {2}, {4}, {4}, {4}, {6,6}, {4,4}, {4,4} and { 4,4,4 } are the subarrays which can be formed with maximum and minimum element same.

Input : array = { 3,3,1,5,1,2,2 }
Output : 9
Explanation : {3}, {3}, {1}, {5}, {1}, {2}, {2}, {3,3} and {2,2} are the subarrays which can be formed with minimum and maximum are the same.

How to solve

By example, we can say that a minimum number of subarrays can be formed using the same minimum and maximum elements equal to the size of the array. The number of subarrays can be greater if consecutive numbers are the same.

So we can use the method of traversing each element and checking whether its consecutive numbers are the same. If the consecutive numbers are the same, the count will be increased. If different numbers are found, the inner loop will be interrupted.

Every time the inner loop ends or is interrupted, the result variable will be incremented, and finally the result variable will be displayed.

p>

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[ ] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = n, count =0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if(a[i]==a[j])
                count++;
            else
                break;
        }
        result+=count;
        count =0;
    }
    cout << "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity = O(n<sup>2</sup>).

Explanation of the above code

In this code, we use the variable n to store the array The size of , result = n, since at least n subarrays can be formed and counts of the same number calculated.

The outer loop is used to process each element in the array. The inner loop is used to find how many consecutive identical numbers there are after the index element and at the end of the inner loop it increments the count variable along with the result variable. Finally the output stored in the result variable is displayed.

Efficient method

In this method, we iterate through each element, and for each element, we search how many consecutive identical numbers there are. For each identical number found, we increment the count variable and when a different number is found, find how many subdivisions can be formed using this formula by using the formula "n = n*(n 1)/2" array and increment the result variable.

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[] = { 2, 4, 5, 3, 3, 3 };
    int n = sizeof(a) / sizeof(a[0]);
        int result = 0;
    int count =1,temp=a[0];
    for (int i = 1; i < n; i++) {
        if (temp==a[i]){
            count++;
        }
        else{
            temp=a[i];
            result = result + (count*(count+1)/2);
            count=1;
        }
    }
    result = result + (count*(count+1)/2);
    cout <<  "Number of subarrays having minimum and maximum elements same:" << result;
    return 0;
}

Output

Number of subarrays having minimum and maximum elements same: 9
Time complexity : O(n)

Description of the above code

In this code, we store the 0th index of the array in the temp variable, And start looping from index 1. We check if the temp variable is equal to the element at the current index and increment the count by 1 for the same number found. If the temp variable is not equal to the index element, we find the combination of subarrays that can be derived by counting the same number and store the result in the result variable. We change the temporary value to the current index, resetting the count to 1. Finally, we display the answer stored in the result variable.

Conclusion

In this article, we solved the problem of finding the number of subarrays with the same minimum and maximum elements. We also learned a C program to solve this problem and a complete way to solve this problem (normal and efficient). We can write the same program in other languages ​​such as C, java, python and other languages. Hope this article is helpful to you.

The above is the detailed content of Write a code using C++ to find the number of subarrays with the same minimum and maximum values. For more information, please follow other related articles on the PHP Chinese website!