Problem

Submissions

Hints & solutions

Discuss

Number of occurrence

Moderate

0/80

Average time to solve is 26m

Contributed by

235 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

7 3
1 1 1 2 2 3 3

Sample Output 1:

Explanation For Sample Input 1:

In the given list, there are 2 occurrences of integer 3.

Sample Input 2:

 5 6
 1 2 4 4 5

Sample Output 2:

Explanation For Sample Input 2:

In the given list, there are 0 occurrences of integer 6.

Expected time complexity:

The expected time complexity is O(log 'n').

Constraints:

1 <= n <= 10^4
1 <= arr[i] <= 10^9
1 <= x <= 10^9
Where arr[i] represents the element i-th element in the array/list.

Time Limit: 1sec

Hint 1

Hint 2

Hint 3

Visit every element in the array and keep a track of whether the element being visited is X or not.

Approaches (3)

Approach 1

Approach 2

Approach 3

Simple Counting Approach

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.

Time Complexity

O(N), Where N is the total number of elements in the array of the size of the array.

You visit every element once, making a total of N operations.

Therefore the time complexity is O(N).

Space Complexity

O(1)

We are using constant extra space.

Therefore the space complexity is O(1).

(100% EXP penalty)

Number of occurrence

Console