Posted on by Kalkicode
Code Divide And Conquer

Find the frequency of a number in an array using divide and conquer

The problem at hand revolves around finding the frequency of a given number in an array using a divide and conquer approach. This technique breaks down complex problems into simpler sub-problems, solves them, and then combines the solutions to solve the original problem. In this case, the objective is to count how many times a specific number appears in a given array.

Problem Statement

Given an array arr of integers and a target number x, we need to determine how many times x occurs within the array. This count will be our desired frequency.

Example

Let's take the array arr1 = [4, 4, 10, 3, 12, 4, 6, 3]. If we want to find the frequency of x = 4, the expected output should be 3, as 4 appears three times in the array.

Idea to Solve

The divide and conquer approach involves dividing the array into smaller parts, solving each part recursively, and then combining the results. To implement this, we can follow these steps:

  1. Divide the array into two halves, left and right.
  2. Recursively count the occurrences of x in the left and right halves.
  3. Combine the counts obtained from the left and right halves to get the total frequency of x in the entire array.

Pseudocode

function countFrequency(arr, low, high, x):
    if low > high:
        return 0
    if low == high:
        if arr[low] == x:
            return 1
        else:
            return 0
    mid = low + (high - low) / 2
    leftCount = countFrequency(arr, low, mid, x)
    rightCount = countFrequency(arr, mid + 1, high, x)
    return leftCount + rightCount

Algorithm Explanation

  • The base cases are when the range low to high is invalid (i.e., low > high) or when we are left with a single element in the range.
  • If there's only one element, we check whether it's equal to x or not. If it is, we return 1 (indicating a match), otherwise 0.
  • If there are multiple elements in the range, we calculate the middle index mid to divide the range into two halves.
  • We then recursively count the occurrences of x in the left and right halves.
  • Finally, we sum up the counts from both halves and return the total count.

Code Solution

// C Program
// Find the frequency of a number in an array using divide and conquer
#include <stdio.h>

int countFrequency(int arr[], int low, int high, int x)
{
    if (low > high)
    {
        return 0;
    }
    if (low == high)
    {
        if (x == arr[low])
        {
            // We get element
            return 1;
        }
        return 0;
    }
    // Find middle element
    int mid = low + ((high - low) / 2);
    // Count element in left and right subtree using recursion
    return countFrequency(arr, low, mid, x) + 
      countFrequency(arr, mid + 1, high, x);
}
int main()
{
    int arr1[] = {
        4 , 4 , 10 , 3 , 12 , 4 , 6 , 3
    };
    int arr2[] = {
        8 , 20 , 16 , 10 , 6
    };
    /*
        arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
    */
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int x = 3;
    printf("\n %d Occurring %d times", x, 
           countFrequency(arr1, 0, n - 1, x));
    x = 4;
    printf("\n %d Occurring %d times", x, 
           countFrequency(arr1, 0, n - 1, x));
    n = sizeof(arr2) / sizeof(arr2[0]);
    /*
        arr2 = [8 , 20 , 16 , 10 , 6]
    */
    x = 16;
    printf("\n %d Occurring %d times", x, 
           countFrequency(arr2, 0, n - 1, x));
    x = 9;
    printf("\n %d Occurring %d times", x, 
           countFrequency(arr2, 0, n - 1, x));
    return 0;
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
// Java Program 
// Find the frequency of a number in an array using divide and conquer
public class Counting
{
	public int countFrequency(int[] arr, int low, int high, int x)
	{
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr[low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		int mid = low + ((high - low) / 2);
		// Count element in left and right subtree using recursion
		return countFrequency(arr, low, mid, x) + 
			countFrequency(arr, mid + 1, high, x);
	}
	public static void main(String args[])
	{
		Counting task = new Counting();
		int[] arr1 =  {
			4 , 4 , 10 , 3 , 12 , 4 , 6 , 3
		};
		int[] arr2 =  {
			8 , 20 , 16 , 10 , 6
		};
		/*
		    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
		*/
		int n = arr1.length;
		int x = 3;
		System.out.print("\n " + x + " Occurring " + 
                         task.countFrequency(arr1, 0, n - 1, x) + " times");
		x = 4;
		System.out.print("\n " + x + " Occurring " + 
                         task.countFrequency(arr1, 0, n - 1, x) + " times");
		n = arr2.length;
		/*
		    arr2 = [8 , 20 , 16 , 10 , 6]
		*/
		x = 16;
		System.out.print("\n " + x + " Occurring " + 
                         task.countFrequency(arr2, 0, n - 1, x) + " times");
		x = 9;
		System.out.print("\n " + x + " Occurring " + 
                         task.countFrequency(arr2, 0, n - 1, x) + " times");
	}
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
// Include header file
#include <iostream>

using namespace std;
// C++ Program
// Find the frequency of a number in an array using divide and conquer
class Counting
{
	public: int countFrequency(int arr[], int low, int high, int x)
	{
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr[low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		int mid = low + ((high - low) / 2);
		// Count element in left and right subtree using recursion
		return this->countFrequency(arr, low, mid, x) + 
          this->countFrequency(arr, mid + 1, high, x);
	}
};
int main()
{
	Counting *task = new Counting();
	int arr1[] = {
		4 , 4 , 10 , 3 , 12 , 4 , 6 , 3
	};
	int arr2[] = {
		8 , 20 , 16 , 10 , 6
	};
	/*
	    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	*/
	int n = sizeof(arr1) / sizeof(arr1[0]);
	int x = 3;
	cout << "\n " << x << " Occurring " 
  		 << task->countFrequency(arr1, 0, n - 1, x) << " times";
	x = 4;
	cout << "\n " << x << " Occurring " 
  		 << task->countFrequency(arr1, 0, n - 1, x) << " times";
	n = sizeof(arr2) / sizeof(arr2[0]);
	/*
	    arr2 = [8 , 20 , 16 , 10 , 6]
	*/
	x = 16;
	cout << "\n " << x << " Occurring " 
         << task->countFrequency(arr2, 0, n - 1, x) << " times";
	x = 9;
	cout << "\n " << x << " Occurring " 
         << task->countFrequency(arr2, 0, n - 1, x) << " times";
	return 0;
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
// Include namespace system
using System;
// Csharp Program
// Find the frequency of a number in an array using divide and conquer
public class Counting
{
	public int countFrequency(int[] arr, 
    int low, 
    int high, 
    int x)
	{
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr[low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		int mid = low + ((high - low) / 2);
		// Count element in left and right subtree using recursion
		return this.countFrequency(arr, low, mid, x) + 
          this.countFrequency(arr, mid + 1, high, x);
	}
	public static void Main(String[] args)
	{
		Counting task = new Counting();
		int[] arr1 = {
			4 , 4 , 10 , 3 , 12 , 4 , 6 , 3
		};
		int[] arr2 = {
			8 , 20 , 16 , 10 , 6
		};
		/*
		    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
		*/
		int n = arr1.Length;
		int x = 3;
		Console.Write("\n " + x + " Occurring " + 
                      task.countFrequency(arr1, 0, n - 1, x) + " times");
		x = 4;
		Console.Write("\n " + x + " Occurring " + 
                      task.countFrequency(arr1, 0, n - 1, x) + " times");
		n = arr2.Length;
		/*
		    arr2 = [8 , 20 , 16 , 10 , 6]
		*/
		x = 16;
		Console.Write("\n " + x + " Occurring " + 
                      task.countFrequency(arr2, 0, n - 1, x) + " times");
		x = 9;
		Console.Write("\n " + x + " Occurring " + 
                      task.countFrequency(arr2, 0, n - 1, x) + " times");
	}
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
package main
import "fmt"
// Go Program
// Find the frequency of a number in an array using divide and conquer
type Counting struct {}
func getCounting() * Counting {
	var me *Counting = &Counting {}
	return me
}
func(this Counting) countFrequency(arr[] int, 
	low int, high int, x int) int {
	if low > high {
		return 0
	}
	if low == high {
		if x == arr[low] {
			// We get element
			return 1
		}
		return 0
	}
	// Find middle element
	var mid int = low + ((high - low) / 2)
	// Count element in left and right subtree using recursion
	return this.countFrequency(arr, low, mid, x) + 
	this.countFrequency(arr, mid + 1, high, x)
}
func main() {
	var task * Counting = getCounting()
	var arr1 = [] int {
		4,
		4,
		10,
		3,
		12,
		4,
		6,
		3,
	}
	var arr2 = [] int {
		8,
		20,
		16,
		10,
		6,
	}
	/*
	    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	*/
	var n int = len(arr1)
	var x int = 3
	fmt.Print("\n ", x, " Occurring ", 
		task.countFrequency(arr1, 0, n - 1, x), " times")
	x = 4
	fmt.Print("\n ", x, " Occurring ", 
		task.countFrequency(arr1, 0, n - 1, x), " times")
	n = len(arr2)
	/*
	    arr2 = [8 , 20 , 16 , 10 , 6]
	*/
	x = 16
	fmt.Print("\n ", x, " Occurring ", 
		task.countFrequency(arr2, 0, n - 1, x), " times")
	x = 9
	fmt.Print("\n ", x, " Occurring ", 
		task.countFrequency(arr2, 0, n - 1, x), " times")
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
<?php
// Php Program
// Find the frequency of a number in an array using divide and conquer
class Counting
{
	public	function countFrequency($arr, $low, $high, $x)
	{
		if ($low > $high)
		{
			return 0;
		}
		if ($low == $high)
		{
			if ($x == $arr[$low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		$mid = $low + ((int)(($high - $low) / 2));
		// Count element in left and right subtree using recursion
		return $this->countFrequency($arr, $low, $mid, $x) + 
          $this->countFrequency($arr, $mid + 1, $high, $x);
	}
}

function main()
{
	$task = new Counting();
	$arr1 = array(4, 4, 10, 3, 12, 4, 6, 3);
	$arr2 = array(8, 20, 16, 10, 6);
	/*
	    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	*/
	$n = count($arr1);
	$x = 3;
	echo("\n ".$x.
		" Occurring ".$task->countFrequency($arr1, 0, $n - 1, $x).
		" times");
	$x = 4;
	echo("\n ".$x.
		" Occurring ".$task->countFrequency($arr1, 0, $n - 1, $x).
		" times");
	$n = count($arr2);
	/*
	    arr2 = [8 , 20 , 16 , 10 , 6]
	*/
	$x = 16;
	echo("\n ".$x.
		" Occurring ".$task->countFrequency($arr2, 0, $n - 1, $x).
		" times");
	$x = 9;
	echo("\n ".$x.
		" Occurring ".$task->countFrequency($arr2, 0, $n - 1, $x).
		" times");
}
main();

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
// Node JS Program
// Find the frequency of a number in an array using divide and conquer
class Counting
{
	countFrequency(arr, low, high, x)
	{
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr[low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		var mid = low + (parseInt((high - low) / 2));
		// Count element in left and right subtree using recursion
		return this.countFrequency(arr, low, mid, x) + 
          this.countFrequency(arr, mid + 1, high, x);
	}
}

function main()
{
	var task = new Counting();
	var arr1 = [4, 4, 10, 3, 12, 4, 6, 3];
	var arr2 = [8, 20, 16, 10, 6];
	/*
	    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	*/
	var n = arr1.length;
	var x = 3;
	process.stdout.write("\n " + x + " Occurring " + 
                         task.countFrequency(arr1, 0, n - 1, x) + " times");
	x = 4;
	process.stdout.write("\n " + x + " Occurring " + 
                         task.countFrequency(arr1, 0, n - 1, x) + " times");
	n = arr2.length;
	/*
	    arr2 = [8 , 20 , 16 , 10 , 6]
	*/
	x = 16;
	process.stdout.write("\n " + x + " Occurring " + 
                         task.countFrequency(arr2, 0, n - 1, x) + " times");
	x = 9;
	process.stdout.write("\n " + x + " Occurring " + 
                         task.countFrequency(arr2, 0, n - 1, x) + " times");
}
main();

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
#  Python 3 Program
#  Find the frequency of a number in an array using divide and conquer
class Counting :
	def countFrequency(self, arr, low, high, x) :
		if (low > high) :
			return 0
		
		if (low == high) :
			if (x == arr[low]) :
				#  We get element
				return 1
			
			return 0
		
		#  Find middle element
		mid = low + (int((high - low) / 2))
		#  Count element in left and right subtree using recursion
		return self.countFrequency(
          arr, low, mid, x
        ) + self.countFrequency(
          arr, mid + 1, high, x
        )
	

def main() :
	task = Counting()
	arr1 = [4, 4, 10, 3, 12, 4, 6, 3]
	arr2 = [8, 20, 16, 10, 6]
	#    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	n = len(arr1)
	x = 3
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr1, 0, n - 1, x) ," times", end = "")
	x = 4
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr1, 0, n - 1, x) ," times", end = "")
	n = len(arr2)
	#    arr2 = [8 , 20 , 16 , 10 , 6]
	x = 16
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr2, 0, n - 1, x) ," times", end = "")
	x = 9
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr2, 0, n - 1, x) ," times", end = "")

if __name__ == "__main__": main()

Output

  3  Occurring  2  times
  4  Occurring  3  times
  16  Occurring  1  times
  9  Occurring  0  times
#  Ruby Program
#  Find the frequency of a number in an array using divide and conquer
class Counting 
	def countFrequency(arr, low, high, x) 
		if (low > high) 
			return 0
		end

		if (low == high) 
			if (x == arr[low]) 
				#  We get element
				return 1
			end

			return 0
		end

		#  Find middle element
		mid = low + ((high - low) / 2)
		#  Count element in left and right subtree using recursion
		return self.countFrequency(arr, low, mid, x) + 
          self.countFrequency(arr, mid + 1, high, x)
	end

end

def main() 
	task = Counting.new()
	arr1 = [4, 4, 10, 3, 12, 4, 6, 3]
	arr2 = [8, 20, 16, 10, 6]
	#    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	n = arr1.length
	x = 3
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr1, 0, n - 1, x) ," times")
	x = 4
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr1, 0, n - 1, x) ," times")
	n = arr2.length
	#    arr2 = [8 , 20 , 16 , 10 , 6]
	x = 16
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr2, 0, n - 1, x) ," times")
	x = 9
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr2, 0, n - 1, x) ," times")
end

main()

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
// Scala Program
// Find the frequency of a number in an array using divide and conquer
class Counting()
{
	def countFrequency(arr: Array[Int], 
      low: Int, high: Int, x: Int): Int = {
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr(low))
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		var mid: Int = low + ((high - low) / 2);
		// Count element in left and right subtree using recursion
		return countFrequency(arr, low, mid, x) + 
          countFrequency(arr, mid + 1, high, x);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Counting = new Counting();
		var arr1: Array[Int] = Array(4, 4, 10, 3, 12, 4, 6, 3);
		var arr2: Array[Int] = Array(8, 20, 16, 10, 6);
		/*
		    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
		*/
		var n: Int = arr1.length;
		var x: Int = 3;
		print("\n " + x + " Occurring " + 
              task.countFrequency(arr1, 0, n - 1, x) + " times");
		x = 4;
		print("\n " + x + " Occurring " + 
              task.countFrequency(arr1, 0, n - 1, x) + " times");
		n = arr2.length;
		/*
		    arr2 = [8 , 20 , 16 , 10 , 6]
		*/
		x = 16;
		print("\n " + x + " Occurring " + 
              task.countFrequency(arr2, 0, n - 1, x) + " times");
		x = 9;
		print("\n " + x + " Occurring " + 
              task.countFrequency(arr2, 0, n - 1, x) + " times");
	}
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times
import Foundation;
// Swift 4 Program
// Find the frequency of a number in an array using divide and conquer
class Counting
{
	func countFrequency(_ arr: [Int], 
    _ low: Int, 
    	_ high: Int, 
      		_ x: Int) -> Int
	{
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr[low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		let mid: Int = low + ((high - low) / 2);
		// Count element in left and right subtree using recursion
		return self.countFrequency(arr, low, mid, x) + 
          self.countFrequency(arr, mid + 1, high, x);
	}
}
func main()
{
	let task: Counting = Counting();
	let arr1: [Int] = [4, 4, 10, 3, 12, 4, 6, 3];
	let arr2: [Int] = [8, 20, 16, 10, 6];
	/*
	    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	*/
	var n: Int = arr1.count;
	var x: Int = 3;
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr1, 0, n - 1, x) ," times", terminator: "");
	x = 4;
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr1, 0, n - 1, x) ," times", terminator: "");
	n = arr2.count;
	/*
	    arr2 = [8 , 20 , 16 , 10 , 6]
	*/
	x = 16;
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr2, 0, n - 1, x) ," times", terminator: "");
	x = 9;
	print("\n ", x ," Occurring ", 
          task.countFrequency(arr2, 0, n - 1, x) ," times", terminator: "");
}
main();

Output

  3  Occurring  2  times
  4  Occurring  3  times
  16  Occurring  1  times
  9  Occurring  0  times
// Kotlin Program
// Find the frequency of a number in an array using divide and conquer
class Counting
{
	fun countFrequency(arr: Array < Int > , 
                        low: Int, 
                        high: Int, 
                        x: Int): Int
	{
		if (low > high)
		{
			return 0;
		}
		if (low == high)
		{
			if (x == arr[low])
			{
				// We get element
				return 1;
			}
			return 0;
		}
		// Find middle element
		val mid: Int = low + ((high - low) / 2);
		// Count element in left and right subtree using recursion
		return this.countFrequency(arr, low, mid, x) + 
          this.countFrequency(arr, mid + 1, high, x);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Counting = Counting();
	val arr1: Array < Int > = arrayOf(4, 4, 10, 3, 12, 4, 6, 3);
	val arr2: Array < Int > = arrayOf(8, 20, 16, 10, 6);
	/*
	    arr1 = [ 4, 4, 10 , 3 , 12 ,4 , 6 , 3]
	*/
	var n: Int = arr1.count();
	var x: Int = 3;
	print("\n " + x + " Occurring " + 
          task.countFrequency(arr1, 0, n - 1, x) + " times");
	x = 4;
	print("\n " + x + " Occurring " + 
          task.countFrequency(arr1, 0, n - 1, x) + " times");
	n = arr2.count();
	/*
	    arr2 = [8 , 20 , 16 , 10 , 6]
	*/
	x = 16;
	print("\n " + x + " Occurring " + 
          task.countFrequency(arr2, 0, n - 1, x) + " times");
	x = 9;
	print("\n " + x + " Occurring " + 
          task.countFrequency(arr2, 0, n - 1, x) + " times");
}

Output

 3 Occurring 2 times
 4 Occurring 3 times
 16 Occurring 1 times
 9 Occurring 0 times

Time Complexity

The time complexity of this algorithm can be analyzed based on the number of recursive calls. In each recursive call, we split the array into two halves. Since each call only considers one half, the maximum number of recursive calls is O(log n), where n is the number of elements in the array. Within each recursive call, we perform constant time operations. Hence, the overall time complexity is O(log n).

Comment

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





Categories
Relative Post