Given an array arr[] of length N, the task is to find the total number of elements that has frequency 1 in a subarray of the given array.

Examples:

Input: N = 3, arr[ ] = {2, 4, 2}
Output:  8
Explanation: All possible subarrays are 
{2}: elements with frequency one = 1.
{4}: elements with frequency one = 1.
{2}: elements with frequency one = 1.
{2, 4}: elements with frequency one = 2.
{4, 2}: elements with frequency one = 2.
{2, 4, 2}: elements with frequency one = 1 (i.e., only for 4).
Total count of elements = 1 + 1 + 1 + 2 + 2 + 1 = 8.

Input: N = 2, arr[ ] = {1, 1}
Output: 2
Explanation: All possible subarrays are 
{1}: elements with frequency one = 1.
{1, 1}: elements with frequency one = 0.
{1}: elements with frequency one = 1.
Total count of elements = 1 + 0 + 1 = 2.

Naive Approach: The simple idea is to calculate all the possible subarrays and for each subarray count the number of elements that are present only once in that subarray and add that count to the final answer.

• Initialize a variable count to 0. This variable will be used to store the total number of elements that have frequency 1 in a subarray of the given array.
• Iterate through all possible subarrays of the given array. For each subarray, do the following:
  • Create an unordered_map to store the frequency of each element in the subarray.
  • Iterate through all elements in the subarray. For each element, increment its frequency in the unordered_map.
  • Iterate through all elements in the unordered_map and check if their frequency is equal to 1. If so, increment the count variable by 1.
• Return the value of count.

Below is the implementation of the above approach:

8

Time Complexity: O(N)
Auxiliary Space: O(N)