Count number of occurrences in a sorted array
Here given code implementation process.
// C Program
// Count number of occurrences in a sorted array
#include <stdio.h>
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//Method which is finding given element index
int binary_search(int arr[], int size, int element)
{
//Defining variables are control execution process of function
int i = 0;
int j = (size - 1);
int mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
void count_occurrences(int arr[], int size, int element)
{
//Find the location of any given element
int location = binary_search(arr, size, element);
printf("\n Array elements : ");
display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
printf(" Element %d are exists [%d] times\n", element, counter);
}
else
{
printf(" Element %d are not exists \n", element);
}
}
int main()
{
int arr1[] = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
count_occurrences(arr1, size, 3);
int arr2[] = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
count_occurrences(arr2, size, 8);
return 0;
}
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
// Java Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
//Method which is finding given element index
public int binary_search(int[] arr, int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
public void count_occurrences(int[] arr, int size, int element)
{
//Find the location of any given element
int location = binary_search(arr, size, element);
System.out.print("\n Array elements : ");
display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
System.out.print(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
System.out.print(" Element " + element + " are not exists \n");
}
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = arr1.length;
obj.count_occurrences(arr1, size, 3);
int[] arr2 = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = arr2.length;
obj.count_occurrences(arr2, size, 8);
}
}
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
//Include header file
#include <iostream>
using namespace std;
// C++ Program
// Count number of occurrences in a sorted array
class MyArray
{
public:
//Function which is display array elements
void display(int arr[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
//Method which is finding given element index
int binary_search(int arr[], int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
void count_occurrences(int arr[], int size, int element)
{
//Find the location of any given element
int location = this->binary_search(arr, size, element);
cout << "\n Array elements : ";
this->display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
cout << " Element " << element << " are exists [" << counter << "] times\n";
}
else
{
cout << " Element " << element << " are not exists \n";
}
}
};
int main()
{
MyArray obj = MyArray();
int arr1[] = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.count_occurrences(arr1, size, 3);
int arr2[] = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = sizeof(arr2) / sizeof(arr2[0]);
obj.count_occurrences(arr2, size, 8);
return 0;
}
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
//Include namespace system
using System;
// C# Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
public void display(int[] arr, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
//Method which is finding given element index
public int binary_search(int[] arr, int size, int element)
{
//Defining variables are control execution process of function
int i = 0, j = (size - 1), mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
public void count_occurrences(int[] arr, int size, int element)
{
//Find the location of any given element
int location = binary_search(arr, size, element);
Console.Write("\n Array elements : ");
display(arr, size);
if (location > 0)
{
int counter = 0;
int temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
//Display result
Console.Write(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
Console.Write(" Element " + element + " are not exists \n");
}
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
-2 , -1 , 2 , 3 , 3 , 3 , 3 , 5 , 5
};
//Get the size of array
int size = arr1.Length;
obj.count_occurrences(arr1, size, 3);
int[] arr2 = {
6 , 7 , 7 , 7 , 8 , 8 , 8 , 8 , 8 , 9 , 9 , 20
};
//Get the size of array
size = arr2.Length;
obj.count_occurrences(arr2, size, 8);
}
}
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
<?php
// Php Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
public function display( & $arr, $size)
{
for ($i = 0; $i < $size; ++$i)
{
echo " ". $arr[$i];
}
echo "\n";
}
//Method which is finding given element index
public function binary_search( & $arr, $size, $element)
{
//Defining variables are control execution process of function
$i = 0;
$j = ($size - 1);
$mid = 0;
//Search intermediate element
while ($j > $i)
{
//Get middle element
$mid = intval(($i + $j) / 2);
if ($arr[$mid] > $element)
{
//When middle element of index i and j are greater
$j = $mid - 1;
}
else if ($arr[$mid] < $element)
{
//When middle element of index i and j are less
$i = $mid + 1;
}
else
{
return $mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
public function count_occurrences( & $arr, $size, $element)
{
//Find the location of any given element
$location = $this->binary_search($arr, $size, $element);
echo "\n Array elements : ";
$this->display($arr, $size);
if ($location > 0)
{
$counter = 0;
$temp = $location;
//Find next similar nodes
while ($temp < $size && $arr[$temp] == $element)
{
$counter++;
$temp++;
}
$temp = $location - 1;
//Find previous similar nodes
while ($temp >= 0 && $arr[$temp] == $element)
{
$counter++;
$temp--;
}
echo " Element ". $element ." are exists [". $counter ."] times\n";
}
else
{
echo " Element ". $element ." are not exists \n";
}
}
}
function main()
{
$obj = new MyArray();
$arr1 = array(-2, -1, 2, 3, 3, 3, 3, 5, 5);
//Get the size of array
$size = count($arr1);
$obj->count_occurrences($arr1, $size, 3);
$arr2 = array(6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20);
//Get the size of array
$size = count($arr2);
$obj->count_occurrences($arr2, $size, 8);
}
main();
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
// Node Js Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
display(arr, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
//Method which is finding given element index
binary_search(arr, size, element)
{
//Defining variables are control execution process of function
var i = 0;
var j = (size - 1);
var mid = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = parseInt((i + j) / 2);
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
count_occurrences(arr, size, element)
{
//Find the location of any given element
var location = this.binary_search(arr, size, element);
process.stdout.write("\n Array elements : ");
this.display(arr, size);
if (location > 0)
{
var counter = 0;
var temp = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter++;
temp++;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter++;
temp--;
}
process.stdout.write(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
process.stdout.write(" Element " + element + " are not exists \n");
}
}
}
function main()
{
var obj = new MyArray();
var arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5];
//Get the size of array
var size = arr1.length;
obj.count_occurrences(arr1, size, 3);
var arr2 = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20];
//Get the size of array
size = arr2.length;
obj.count_occurrences(arr2, size, 8);
}
main();
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
# Python 3 Program
# Count number of occurrences in a sorted array
class MyArray :
# Function which is display array elements
def display(self, arr, size) :
i = 0
while (i < size) :
print(" ", arr[i], end = "")
i += 1
print("\n", end = "")
# Method which is finding given element index
def binary_search(self, arr, size, element) :
# Defining variables are control execution process of function
i = 0
j = (size - 1)
mid = 0
# Search intermediate element
while (j > i) :
# Get middle element
mid = int((i + j) / 2)
if (arr[mid] > element) :
# When middle element of index i and j are greater
j = mid - 1
elif(arr[mid] < element) :
# When middle element of index i and j are less
i = mid + 1
else :
return mid
return -1
# Find the occurrence of elements in given sorted array
def count_occurrences(self, arr, size, element) :
# Find the location of any given element
location = self.binary_search(arr, size, element)
print("\n Array elements : ", end = "")
self.display(arr, size)
if (location > 0) :
counter = 0
temp = location
# Find next similar nodes
while (temp < size and arr[temp] == element) :
counter += 1
temp += 1
temp = location - 1
# Find previous similar nodes
while (temp >= 0 and arr[temp] == element) :
counter += 1
temp -= 1
print(" Element ", element ," are exists [", counter ,"] times\n", end = "")
else :
print(" Element ", element ," are not exists \n", end = "")
def main() :
obj = MyArray()
arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5]
# Get the size of array
size = len(arr1)
obj.count_occurrences(arr1, size, 3)
arr2 = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20]
# Get the size of array
size = len(arr2)
obj.count_occurrences(arr2, size, 8)
if __name__ == "__main__": main()
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [ 4 ] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [ 5 ] times
# Ruby Program
# Count number of occurrences in a sorted array
class MyArray
# Function which is display array elements
def display(arr, size)
i = 0
while (i < size)
print(" ", arr[i])
i += 1
end
print("\n")
end
# Method which is finding given element index
def binary_search(arr, size, element)
# Defining variables are control execution process of function
i = 0
j = (size - 1)
mid = 0
# Search intermediate element
while (j > i)
# Get middle element
mid = (i + j) / 2
if (arr[mid] > element)
# When middle element of index i and j are greater
j = mid - 1
elsif(arr[mid] < element)
# When middle element of index i and j are less
i = mid + 1
else
return mid
end
end
return -1
end
# Find the occurrence of elements in given sorted array
def count_occurrences(arr, size, element)
# Find the location of any given element
location = self.binary_search(arr, size, element)
print("\n Array elements : ")
self.display(arr, size)
if (location > 0)
counter = 0
temp = location
# Find next similar nodes
while (temp < size && arr[temp] == element)
counter += 1
temp += 1
end
temp = location - 1
# Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
counter += 1
temp -= 1
end
# Display result
print(" Element ", element ," are exists [", counter ,"] times\n")
else
print(" Element ", element ," are not exists \n")
end
end
end
def main()
obj = MyArray.new()
arr1 = [-2, -1, 2, 3, 3, 3, 3, 5, 5]
# Get the size of array
size = arr1.length
obj.count_occurrences(arr1, size, 3)
arr2 = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20]
# Get the size of array
size = arr2.length
obj.count_occurrences(arr2, size, 8)
end
main()
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
// Scala Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
def display(arr: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
//Method which is finding given element index
def binary_search(arr: Array[Int], size: Int, element: Int): Int = {
//Defining variables are control execution process of function
var i: Int = 0;
var j: Int = (size - 1);
var mid: Int = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = ((i + j) / 2).toInt;
if (arr(mid) > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr(mid) < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
def count_occurrences(arr: Array[Int], size: Int, element: Int): Unit = {
//Find the location of any given element
var location: Int = binary_search(arr, size, element);
print("\n Array elements : ");
display(arr, size);
if (location > 0)
{
var counter: Int = 0;
var temp: Int = location;
//Find next similar nodes
while (temp < size && arr(temp) == element)
{
counter += 1;
temp += 1;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr(temp) == element)
{
counter += 1;
temp -= 1;
}
//Display result
print(" Element " + element + " are exists [" + counter + "] times\n");
}
else
{
print(" Element " + element + " are not exists \n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
var arr1: Array[Int] = Array(-2, -1, 2, 3, 3, 3, 3, 5, 5);
//Get the size of array
var size: Int = arr1.length;
obj.count_occurrences(arr1, size, 3);
var arr2: Array[Int] = Array(6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20);
//Get the size of array
size = arr2.length;
obj.count_occurrences(arr2, size, 8);
}
}
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [4] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [5] times
// Swift Program
// Count number of occurrences in a sorted array
class MyArray
{
//Function which is display array elements
func display(_ arr: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
//Method which is finding given element index
func binary_search(_ arr: [Int], _ size: Int, _ element: Int) -> Int
{
//Defining variables are control execution process of function
var i: Int = 0;
var j: Int = (size - 1);
var mid: Int = 0;
//Search intermediate element
while (j > i)
{
//Get middle element
mid = (i + j) / 2;
if (arr[mid] > element)
{
//When middle element of index i and j are greater
j = mid - 1;
}
else if (arr[mid] < element)
{
//When middle element of index i and j are less
i = mid + 1;
}
else
{
return mid;
}
}
return -1;
}
// Find the occurrence of elements in given sorted array
func count_occurrences(_ arr: [Int], _ size: Int, _ element: Int)
{
//Find the location of any given element
let location: Int = self.binary_search(arr, size, element);
print("\n Array elements : ", terminator: "");
self.display(arr, size);
if (location > 0)
{
var counter: Int = 0;
var temp: Int = location;
//Find next similar nodes
while (temp < size && arr[temp] == element)
{
counter += 1;
temp += 1;
}
temp = location - 1;
//Find previous similar nodes
while (temp >= 0 && arr[temp] == element)
{
counter += 1;
temp -= 1;
}
print(" Element ", element ," are exists [", counter ,"] times\n", terminator: "");
}
else
{
print(" Element ", element ," are not exists \n", terminator: "");
}
}
}
func main()
{
let obj: MyArray = MyArray();
let arr1: [Int] = [-2, -1, 2, 3, 3, 3, 3, 5, 5];
//Get the size of array
var size: Int = arr1.count;
obj.count_occurrences(arr1, size, 3);
let arr2: [Int] = [6, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 20];
//Get the size of array
size = arr2.count;
obj.count_occurrences(arr2, size, 8);
}
main();
Output
Array elements : -2 -1 2 3 3 3 3 5 5
Element 3 are exists [ 4 ] times
Array elements : 6 7 7 7 8 8 8 8 8 9 9 20
Element 8 are exists [ 5 ] times
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment