Given an array with all distinct elements, you need to find the occurrence of every element among all the possible subarrays of the array.
Examples:
Input: arr[] = { 2 , 1 , 3 }
Output: 3,4,3
Explanation :
All the possible subarrays are {2},{2,1},{2,1,3},{1},{1,3},{3}.
Clearly 2 occurs 3 times 1 occurs 4 times and 3 occurs 3 times.
Input: arr[] = { 1 , 2 }
Output: 2,2
Explanation :
The possible subarrays are {1},{1,2},{2}. where 2 and 1 both occur 2 time each.
The problem can be solved using concepts of permutation and combination. For each ‘i’th element in the array if it needs to be included in any subarray the starting position of the subarray should be at before or at the ‘i’th index and the ending index should be at ‘i’th or after that.
Therefore the number of choices for a given element at i th position is Choices = ( i + 1 ) * ( n – i ) . for ( 0 based indexing ) as for the ith index we have ( 0. . . i-1 , i ) choices that is (i+1) at the left for the starting position of the subarray while we have ( i , i+1, . . . n ) choices at the right that is ( n – i ) for the ending index of the subarray.
Implementation:
#include <iostream>
using namespace std;
void print_occurrence(int arr[], int size) {
for (int i = 0; i < size; i++) {
// Choices at the left for the left point of subarray are (i+1).
// Choices at the right for the right point of subarray are (size-i).
cout << (i + 1) * (size - i) << " ";
}
}
int main() {
int arr[] = {2, 1, 3, 4, 5};
int size = sizeof(arr) / sizeof(int);
print_occurrence(arr, size);
return 0;
}
Output:
5 8 9 8 5