Occurrence of X in a Sorted Array.
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

Question

Occurrence of X in a Sorted Array.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant extra space.

Time Complexity: O(n)Explanation:

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

You visit every element once, hence you make a total of N operations. therefore the time complexity is O(N).

Accepted Answer

Binary Search

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.

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant extra space.

Time Complexity: O(n)Explanation:

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

The worst case of this approach would be when all elements of the array are equal to the element we want to count the occurrences of. Therefore the time complexity is O(N).

Accepted Answer

Smart Binary Search

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).

Space Complexity: O(1)Explanation:

O(1)

Since we are using constant extra space.

Time Complexity: O(logn)Explanation:

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

Since we are performing a binary search over the array, therefore the time complexity is O(log(N)).

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

Output Format

Note:

Constraints:

Top Directi Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Directi Software Developer