Last Updated: 22 Jul, 2020
Number of occurrence
Moderate
Asked in companies
You have been given a sorted array/list of integers 'arr' of size 'n' and an integer 'x'.
Find the total number of occurrences of 'x' in the array/list.
Example:
Input: 'n' = 7, 'x' = 3
'arr' = [1, 1, 1, 2, 2, 3, 3]
Output: 2
Explanation: Total occurrences of '3' in the array 'arr' is 2.
Input Format
The first line of the input contains two integers, n, and x. They represent the size of the array/list and x, respectively.
The second line contains n single space-separated integer representing the array/list elements.
Output Format
Return the total number of occurrences of x in the array/list.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Approaches
- Initialize a count variable with 0 initially, to keep track of the total number of occurrences of X.
- Visit every element one by one in the sorted array and increase the count by 1 if the element being visited is X.
- Once all the elements have been visited, we can return the count.
- Use binary search to find the first occurrence of X, say the index at which X is found be ‘xPos’.
- If ‘xPos’ is -1, then X doesn’t exist in the array and hence we return 0.
- But if it is not the case, then count the number of occurrences of X to the left and right of ‘xPos’ and return the total count.
- Use Binary search to get an index of the first occurrence of X in the input Array. Say the index at which X appeared first as ‘xStartIndex’.
- Use Binary search to get an index of the last occurrence of X in the input Array. Say the index at which X appeared last as ‘xEndIndex’.
- Return (xEndIndex – xStartIndex + 1).
Similar problems