Count Frequency of a Number in a Sorted Array.
Given a sorted array and a number k. We have to write a code to count how many times a number k appears in a sorted array.
For example –
Input: { 1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13 }, k = 11
Output: 4
In this input array, The number 11 appears Four time.
In this tutorial, I am going discuss multiple approaches and their time complexities to solve this problem.
Also, i have shared the video tutorial at the end of this post.
Count Number of Occurrences in Array using Linear Search – Java Code
The simplest approach is to traverse an array from left to right. Increment the value of count when current array element is equal to the number k.
The time complexity of this approach is O(n).
Let’s write a java code to implement this approach.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
//Count how many times a number appears in an array. public class CountOccurrence { public static int countOccurrenceUsingLinearSearch(int[] arr, int target) { int count = 0; //Traverse an array for(int i = 0; i < arr.length; i++) { if(arr[i] == target) { count++; } } return count; } public static void main(String[] args) { int arr[] = { 1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13 }; int search = 11; System.out.println(countOccurrenceUsingLinearSearch(arr, search)); } } |
Count Frequency of a Number in a Sorted Array using Binary Search – Java Code
The array is sorted. We can use Binary search to find the first and last position of a number k in this sorted array.
Once the first and last position of a number is found in an array. We can easily calculate the number of occurrences. The number of occurrences is (lastPosition – firstPosition) + 1.
This approach is similar to find first and last position of a number in a sorted array
The time complexity of this approach is O(logn).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
/* Count frequency of a number in a sorted array using binary search. */ public class CountOccurrence { public static int countOccurrenceUsingBinarySearch(int[] arr, int target) { int firstIndex = findFirstPosition(arr, target); int lastIndex = findLastPosition(arr, target); return (lastIndex - firstIndex) + 1; } public static int findFirstPosition(int arr[], int target) { int start = 0; int end = arr.length - 1; int index = -1; while (start <= end) { int mid = (start + end) / 2; if (arr[mid] == target) { index = mid; end = mid - 1; } else if (arr[mid] > target) { end = mid - 1; } else { start = mid + 1; } } return index; } public static int findLastPosition(int arr[], int target) { int start = 0; int end = arr.length - 1; int index = -1; while (start <= end) { int mid = (start + end) / 2; if (arr[mid] == target) { index = mid; start = mid + 1; } else if (arr[mid] > target) { end = mid - 1; } else { start = mid + 1; } } return index; } public static void main(String[] args) { int arr[] = { 1, 4, 7, 8, 8, 11, 11, 11, 11, 12, 13 }; int search = 11; System.out.println(countOccurrenceUsingBinarySearch(arr, search)); } } |
