...

/

Solution: Count Element Occurrence

Solution: Count Element Occurrence

Here is a detailed analysis of the different ways to count the frequency of a number in a sorted array of integers.

Solution #1: Brute force with linear search

Press + to interact
class Count {
public static int calcFreq(int arr[], int key) {
int count = 0;
//traversing the array
for (int i = 0; i < arr.length; i++) {
//checking if current index value matches key
if (arr[i] == key)
//incrementing count if it does
count++;
}
return count;
}
public static void main(String args[]) {
int arr[] = {-5,-3,0,1,3,3,3,3,4,5};
int key = 3;
System.out.println("The key \"" + key + "\" occurs " + calcFreq(arr, key) + " times in the Array.");
}
}

This is an extremely simple way to solve this problem. We simply initialize a variable, count, to keep count and set it to 0 (line 3). We then iterate over the array (line 5), increasing count by one every time the key (value to search) is encountered (lines 7-9).

Time complexity

The time complexity of this algorithm is in O(n)O(n) since the array is iterated over once.

Solution #2: Using binary search

Press + to interact
main.java
Helper.java
class Count
{
public static int calcFreq(int[]arr, int key)
{
int arrSize = arr.length;
Helper obj = new Helper();
int index = obj.binarySearch(key, arr, arrSize);
if (index == -1) // If element is not present
return 0;
int count = 1; // Initialzing a count
int start = index - 1; // Counting the ones present on the left
while (start >= 0 && arr[start] == key) {
count++;
start--; // Decrement the start index if found
}
int end = index + 1; // Counting the ones present on the right
while (end < arrSize && arr[end] == key) {
count++;
end++; // Increment the end index if found
}
return count;
}
public static void main(String args[])
{
int arr[] = {-5,-3,0,1,3,3,3,3,4,5};
int key = 3;
System.out.println("The key \""+ key + "\" occurs " + calcFreq(arr, key) + " times in the Array.");
}
}

This is also a very simple solution. It draws upon the fact that if an element exists in a sorted array, all of its ...