Code:
import java.util.Scanner;
public class NumberOfOccurences
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Enter number of elements in sorted array");
int N = scan.nextInt();
int[] arr = new int[ N ];
/* Accept N elements */
System.out.println("Enter "+ N +" sorted elements");
for (int i = 0; i < N; i++)
arr[i] = scan.nextInt();
System.out.println("Enter number to find occurences");
int num = scan.nextInt();
int f = occur(arr, num);
if (f == -1)
System.out.println("No occurence");
else
System.out.println("Occurences = "+ f);
}
public static int occur(int[] arr, int num)
{
/* find first index */
int l1 = first(arr, num);
/* find last index */
int l2 = last(arr, num);
if (l1 == -1 || l2 == -1)
return -1;
return l2 - l1 + 1;
}
public static int first(int[] arr, int num)
{
if (arr[0] == num)
return 0;
int start = 0, end = arr.length - 1;
int mid = (start + end) / 2;
int flag = 0;
while (!(arr[mid] == num && arr[mid - 1] < arr[mid]))
{
if (start == end)
{
flag = 1;
break;
}
if (arr[mid] >= num)
end = mid - 1;
if (arr[mid] < num)
start = mid + 1;
mid = (start + end) / 2;
}
if (flag == 0)
return mid;
return -1;
}
public static int last(int[] arr, int num)
{
if (arr[arr.length - 1] == num)
return arr.length - 1;
int start = 0, end = arr.length - 1;
int mid = (start + end) / 2;
int flag = 0;
while (!(arr[mid] == num && arr[mid + 1] > arr[mid]))
{
if (start == end)
{
flag = 1;
break;
}
if (arr[mid] > num)
end = mid - 1;
if (arr[mid] <= num)
start = mid + 1;
mid = (start + end) / 2;
}
if (flag == 0)
return mid;
return -1;
}
}
Output:
Enter number of elements in sorted array
10
Enter 10 sorted elements
1 1 3 3 3 3 4 4 4 5
Enter number to find occurences
3
Occurences = 4
Enter number of elements in sorted array
10
Enter 10 sorted elements
1 1 3 3 3 3 4 4 4 5
Enter number to find occurences
5
Occurences = 1
More Java Programs:
