The following solutions describe how to count the number of occurrences of a particular element in a sorted array in which the elements are repeated.
- Using Linear Search algorithm
- Using Binary Search algorithm to find the element and count its occurrences
- Using Binary Search algorithm to find the first occurrence and last occurrence of the element and count the total number of occurrences
Using Linear Search algorithm
Do a linear search over the array and increment count as and when you find the element ‘K’ in the array
Time Complexity – O(n)
Dry run for the following example:
Input: a[8] = {1,2,3,4,4,4,4,5} and K = 4
count = 0;
i=0: a[0] = 1 <> 4. So count = 0
i=1: a[1] = 2 <> 4. So count = 0
i=2: a[2] = 3 <> 4. So count = 0
i=3: a[3] = 4 = 4. So count = 1
i=4: a[4] = 4 = 4. So count = 2
i=5: a[5] = 4 = 4. So count = 3
i=6: a[6] = 4 = 4. So count = 4
i=7: a[7] = 5 <> 4. So count = 4
Total number of occurrences for element 4 is count = 4
Code for the above problem is as follows:
public class LinearSearchCount { public LinearSearchCount() { } public static int countNumberOfOccurances(int[] a, int n, int k) { int resultSearchValue = linearSearchCount(a, n, k); if (resultSearchValue == -1) { return 0; } else { return resultSearchValue; } } public static int linearSearchCount(int[] a, int n, int k) { int count = 0; for (int i = 0; i < n; i++) { if (a[i] == k) { count++; } } return count; } public static void main(String[] args) { // Input Array int[] a = { 1, 2, 3, 4, 4, 4, 4, 5 }; // k - Element to be found int k = 4; // n - Size of the array int n = 8; System.out.println(countNumberOfOccurances(a, n , k)); } }
Using Binary Search algorithm to find the element and count its occurrences
Do a binary search for the element ‘K’ in the array. Let its position be i.
Now traverse towards left and count the number of occurrences of K. Let this count be leftCount.
Similarly, traverse towards right and count the number of occurrences of K. Let this count be rightCount.
Total number of occurrences – leftCount + 1 + rightCount
Time Complexity – O(logn + S) where S is the number of occurrences
Dry run for the following example:
Input: a[8] = {1,2,3,4,4,4,4,5} and K = 4
Binary search to find i:
Iteration 1: low = 0; high = 7; mid = 3
a[3] = 4 = 4. Return mid as 3;
Therefore i =3.
Traverse towards left:
a[i-1] = a[2] = 3 <> 4. leftCount = 0 and stop traversing left
Therefore leftCount =0.
Traverse towards right:
a[i+1] = a[4] = 4 == 4. rightCount = 1
a[i+1] = a[5] = 4 == 4. rightCount = 2
a[i+1] = a[6] = 4 == 4. rightCount = 3
a[i+1] = a[7] = 5 <> 4. rightCount = 3 and stop traversing right
Therefore rightCount = 3.
Total number of occurrences = leftCount + 1 + rightCount = 0 + 1 + 3 = 4
Code for the above problem is as follows:
public class BinaryLinearSearch { public BinaryLinearSearch() { } public static int countNumberOfOccurances(int[] a, int n, int k) { int i = binarySearch(a, 0, n - 1, k); if (i == -1) { return 0; } else { int leftCount = 0; if ((i - 1) > 0) { for (int j = i - 1; j >= 0; j--) { if (a[j] == k) { leftCount++; } else { break; } } } int rightCount = 0; if ((i + 1) < n) { for (int j = i + 1; j <= n; j++) { if (a[j] == k) { rightCount++; } else { break; } } } return leftCount + 1 + rightCount; } } public static int binarySearch(int[] a, int low, int high, int k) { if (high >= low) { int mid = (low + high) / 2; if (a[mid] == k) { return mid; } else if (a[mid] < k) { return binarySearch(a, mid + 1, high, k); } else { return binarySearch(a, low, mid - 1, k); } } return -1; } public static void main(String[] args) { // Input Array int[] a = { 1, 2, 3, 4, 5, 5, 5, 6 }; // k - Element to be found int k = 5; // n - Size of the array int n = 8; System.out.println(countNumberOfOccurances(a, n, k)); } }
Using Binary Search algorithm to find the first occurrence and last occurrence of the element and count the total number of occurrences
To find first Occurrence:
Condition for binary search to find first occurrence is as follows:
Return the position if any one of the following is true:
mid == 0 and a[mid] == K
a[mid] == K and a[mid-1] < K
To find last Occurrence:
Condition for binary search to find last occurrence is as follows:
Return the position if any one of the following is true:
mid == n and a[mid] == K where n is lenght of the array – 1
a[mid] == K and a[mid+1] > K
Total number of occurrences = lastOccurrence – firstOccurrence + 1
Time Complexity – O(log n)
Code for the above problem is as follows:
public class BinarySearchCount { public BinarySearchCount() { } public static int countNumberOfOccurances(int[] a, int n, int k) { int firstOccurrence = binarySearchfirstOccurrence(a, n, 0, n, k); int lastOccurrence = binarySearchlastOccurrence(a, n, 0, n, k); if ((firstOccurrence == -1) && (lastOccurrence == -1)) { return 0; } else if (firstOccurrence == lastOccurrence) { return 1; } else { return (lastOccurrence - firstOccurrence + 1); } } public static int binarySearchfirstOccurrence(int[] a, int n, int low, int high, int k) { if (high >= low) { int mid = (low + high) / 2; if (((mid == 0) && (a[mid] == k)) || ((a[mid] == k) && (a[mid - 1] < k))) { return mid; } // Favor left half of the array else if (a[mid] >= k) { return binarySearchfirstOccurrence(a, n, low, mid - 1, k); } else { return binarySearchfirstOccurrence(a, n, mid + 1, high, k); } } return -1; } public static int binarySearchlastOccurrence(int[] a, int n, int low, int high, int k) { if (high >= low) { int mid = (low + high) / 2; if (((mid == n) && (a[mid] == k)) || ((a[mid] == k) && (a[mid + 1] > k))) { return mid; } // Favor right half of the array else if (a[mid] <= k) { return binarySearchlastOccurrence(a, n, mid + 1, high, k); } else { return binarySearchlastOccurrence(a, n, low, mid - 1, k); } } return -1; } public static void main(String[] args) { // Input Array int[] a = { 1, 2, 3, 4, 5, 5, 5, 6 }; // k - Element to be found int k = 5; // n - Size of the array int n = 8; System.out.println(countNumberOfOccurances(a, n - 1, k)); } }
Please write comments if you find any of the above algorithms or codes incorrect, or find better ways to solve the same problem.
good post!
[…] Count the number of occurrences of a element in a sorted array March 20101 comment 5 […]
what would be the result if you {1,2,3,44,44,4,4,5} in staed of {1,2,3,4,4,4,4,5? Will your logic show the result 6 instead of 4?
@Vivek.. it will not the primary condition of problem..sortey array..
[…] https://crackinterviewtoday.wordpress.com/2010/03/05/count-the-number-of-occurrences-of-a-element-in-… […]
Hi
Actually i need an algorithm which behaves as follows:
Suppose we have elements say A,B,C,X,A,D,A,B
So the slgorithm should find the occurences of each alphabet and then skip the element so that no.of searches steps should b minimised