# Occurrence of X in a Sorted Array

Posted: 22 Jul, 2020

Difficulty: Easy

#### You have been given a sorted array/list of integers of size N and an integer X. Find the total number of occurrences of X in the array/list.

##### 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

```
The only line of output will print 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.
```

##### Constraints:

```
1 <= N <= 10^5
1 <= Arr[i] <= 10^9
Where Arr[i] represents the element i-th element in the array/list.
Time Limit: 1sec
```

Approach 1

Approach 2

Approach 3

- 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

# Lexicographic Permutation Rank

Posted: 13 Jul, 2021

Difficulty: Moderate

# Zero Pair Sum

Posted: 22 Jul, 2021

Difficulty: Moderate

# Longest Common Prefix

Posted: 24 Jul, 2021

Difficulty: Moderate

# Implement a Queue

Posted: 27 Jul, 2021

Difficulty: Easy

# Remove K Corner Elements

Posted: 31 Jul, 2021

Difficulty: Easy