Problem Statement: You are given a sorted array containing N integers and a number X, you have to find the occurrences of X in the given array.
Examples:
Example 1: Input: N = 7, X = 3 , array[] = {2, 2 , 3 , 3 , 3 , 3 , 4} Output: 4 Explanation: 3 is occurring 4 times in the given array so it is our answer. Example 2: Input: N = 8, X = 2 , array[] = {1, 1, 2, 2, 2, 2, 2, 3} Output: 5 Explanation: 2 is occurring 5 times in the given array so it is our answer.
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Using linear search
Approach:
The approach is simple. We will linearly search the entire array, and try to increase the counter whenever we get the target value in the array. Using a for loop that runs from 0 to n – 1, containing an if the condition that checks whether the value at that index equals target. If true then increase the counter, at last return the counter.
Code:
C++ Code
#include <iostream>
using namespace std;
int count(int arr[], int n, int x) {
int k = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
k++;
}
}
return k;
}
int main() {
int n = 7;
int x = 3;
int arr[] = {2,2,3,3,3,3,4};
int ans = count(arr, n, x);
cout <<x<<" occurs "<<ans<<" times in the array" << endl;
}
Output: 3 occurs 4 times in the array
Time Complexity: O(N)
Space Complexity: O(1)
Java Code
import java.io.*;
class TUF {
public static int count(int[] arr, int n, int x) {
int k = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x) {
k++;
}
}
return k;
}
public static void main(String[] args) {
int n = 7;
int x = 3;
int[] arr = {2,2,3,3,3,3,4};
int ans = count(arr, n, x);
System.out.println(x+" occurs "+ans+" times in the array");
}
}
Output: 3 occurs 4 times in the array
Time Complexity: O(N)
Space Complexity: O(1)
Solution 2: Using Binary search
Approach: This approach uses Binary Search to find the index of the X. Then checks the left and right half of the array for getting more occurrences of X.
Call a function that uses Binary search to determine the index of the X in the array, and return the index.
Now we must check for the first occurrences of X at the left and right half of the array.
Increase the counter if X exists at the left and right half of the array. At last return the counter.
Code:
C++ Code
#include <iostream>
#include <iostream>
using namespace std;
int binary(int arr[], int n, int x) {
int s = 0;
int e = n - 1;
while (s <= e) {
int m = (s + e) / 2;
if (arr[m] == x) {
return m;
} else if (arr[m] < x) {
s = m + 1;
} else {
e = m - 1;
}
}
return -1;
}
int count(int arr[], int n, int x) {
// code here
// get the index of X in array
int idx = binary(arr, n, x);
// if X does not exist return 0;
if (idx == -1) {
return 0;
}
int k = 1;
int left = idx - 1;
// check left half for X
while (left >= 0 && arr[left] == x) {
k++;
left--;
}
// check right half for X
int right = idx + 1;
while (right < n && arr[right] == x) {
k++;
right++;
}
return k;
}
int main() {
int n = 7;
int x = 3;
int arr[] = {2,2,3,3,3,3,4};
int ans = count(arr, n, x);
cout <<x<<" occurs "<<ans<<" times in the array" << endl;
}
Output: 3 occurs 4 times in the array
Time Complexity: O(logN)
Space Complexity: O(1)
Java Code
import java.io.*;
class TUF {
public static int binary(int[] arr, int n, int x) {
int s = 0;
int e = arr.length - 1;
while (s <= e) {
int m = (s + e) / 2;
if (arr[m] == x) {
return m;
} else if (arr[m] < x) {
s = m + 1;
} else {
e = m - 1;
}
}
return -1;
}
public static int count(int[] arr, int n, int x) {
// code here
// get the index of X in array
int idx = binary(arr, n, x);
// if X does not exist return 0;
if (idx == -1) {
return 0;
}
int k = 1;
int left = idx - 1;
// check left half for X
while (left >= 0 && arr[left] == x) {
k++;
left--;
}
// check right half for X
int right = idx + 1;
while (right < n && arr[right] == x) {
k++;
right++;
}
return k;
}
public static void main(String[] args) {
int n = 7;
int x = 3;
int[] arr = {2,2,3,3,3,3,4};
int ans = count(arr, n, x);
System.out.println(x+" occurs "+ans+" times in the array");
}
}
Output: 3 occurs 4 times in the array
Time Complexity: O(logN)
Space Complexity: O(1)
Special thanks to Rushikesh Yadav for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article