Skip to main content

Find the smallest missing number in sorted array

Here given code implementation process.

/*
    C program for
    Find the smallest missing number in sorted array
*/
#include <stdio.h>

// Find a smallest missing number in distinct sorted array  
int smallestMissingNo(int arr[], int low, int high)
{
	if (low <= high)
	{
		// Find middle position of given range
		int mid = low + (high - low) / 2;
		if (arr[mid] == mid)
		{
			// When mid index contains same value
			// Change range mid+1 to high
			return smallestMissingNo(arr, mid + 1, high);
		}
		// Change range low to mid-1
		return smallestMissingNo(arr, low, mid - 1);
	}
	else
	{
		// When low value is largest to high
		return low;
	}
}
int main(int argc, char
	const *argv[])
{
	int arr1[] = {
		0 , 1 , 2 , 3 , 4 , 7 , 11 , 17
	};
	int arr2[] = {
		0 , 1 , 2 , 3
	};
	int arr3[] = {
		1 , 2 , 3
	};
	// Test A
	int n = sizeof(arr1) / sizeof(arr1[0]);
	printf("\n %d", smallestMissingNo(arr1, 0, n - 1));
	// Test B
	n = sizeof(arr2) / sizeof(arr2[0]);
	printf("\n %d", smallestMissingNo(arr2, 0, n - 1));
	// Test C
	n = sizeof(arr3) / sizeof(arr3[0]);
	printf("\n %d", smallestMissingNo(arr3, 0, n - 1));
	return 0;
}

Output

 5
 4
 0
/*
    Java program for
    Find the smallest missing number in sorted array
*/
public class MissingNumber
{
	// Find a smallest missing number in distinct sorted array  
	public int smallestMissingNo(int[] arr, int low, int high)
	{
		if (low <= high)
		{
			// Find middle position of given range
			int mid = low + (high - low) / 2;
			if (arr[mid] == mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return smallestMissingNo(arr, mid + 1, high);
			}
			// Change range low to mid-1
			return smallestMissingNo(arr, low, mid - 1);
		}
		else
		{
			// When low value is largest to high
			return low;
		}
	}
	public static void main(String args[])
	{
		MissingNumber task = new MissingNumber();
		// Array of positive distinct elements
		int[] arr1 = {
			0 , 1 , 2 , 3 , 4 , 7 , 11 , 17
		};
		int[] arr2 = {
			0 , 1 , 2 , 3
		};
		int[] arr3 = {
			1 , 2 , 3
		};
		// Test A
		int n = arr1.length;
		System.out.print("\n " + task.smallestMissingNo(arr1, 0, n - 1));
		// Test B
		n = arr2.length;
		System.out.print("\n " + task.smallestMissingNo(arr2, 0, n - 1));
		// Test C
		n = arr3.length;
		System.out.print("\n " + task.smallestMissingNo(arr3, 0, n - 1));
	}
}

Output

 5
 4
 0
// Include header file
#include <iostream>

using namespace std;
/*
    C++ program for
    Find the smallest missing number in sorted array
*/
class MissingNumber
{
	public:
		// Find a smallest missing number in distinct sorted array  
		int smallestMissingNo(int arr[], int low, int high)
		{
			if (low <= high)
			{
				// Find middle position of given range
				int mid = low + (high - low) / 2;
				if (arr[mid] == mid)
				{
					// When mid index contains same value
					// Change range mid+1 to high
					return this->smallestMissingNo(arr, mid + 1, high);
				}
				// Change range low to mid-1
				return this->smallestMissingNo(arr, low, mid - 1);
			}
			else
			{
				// When low value is largest to high
				return low;
			}
		}
};
int main()
{
	MissingNumber *task = new MissingNumber();
	// Array of positive distinct elements
	int arr1[] = {
		0 , 1 , 2 , 3 , 4 , 7 , 11 , 17
	};
	int arr2[] = {
		0 , 1 , 2 , 3
	};
	int arr3[] = {
		1 , 2 , 3
	};
	// Test A
	int n = sizeof(arr1) / sizeof(arr1[0]);
	cout << "\n " << task->smallestMissingNo(arr1, 0, n - 1);
	// Test B
	n = sizeof(arr2) / sizeof(arr2[0]);
	cout << "\n " << task->smallestMissingNo(arr2, 0, n - 1);
	// Test C
	n = sizeof(arr3) / sizeof(arr3[0]);
	cout << "\n " << task->smallestMissingNo(arr3, 0, n - 1);
	return 0;
}

Output

 5
 4
 0
// Include namespace system
using System;
/*
    Csharp program for
    Find the smallest missing number in sorted array
*/
public class MissingNumber
{
	// Find a smallest missing number in distinct sorted array  
	public int smallestMissingNo(int[] arr, int low, int high)
	{
		if (low <= high)
		{
			// Find middle position of given range
			int mid = low + (high - low) / 2;
			if (arr[mid] == mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return this.smallestMissingNo(arr, mid + 1, high);
			}
			// Change range low to mid-1
			return this.smallestMissingNo(arr, low, mid - 1);
		}
		else
		{
			// When low value is largest to high
			return low;
		}
	}
	public static void Main(String[] args)
	{
		MissingNumber task = new MissingNumber();
		// Array of positive distinct elements
		int[] arr1 = {
			0 , 1 , 2 , 3 , 4 , 7 , 11 , 17
		};
		int[] arr2 = {
			0 , 1 , 2 , 3
		};
		int[] arr3 = {
			1 , 2 , 3
		};
		// Test A
		int n = arr1.Length;
		Console.Write("\n " + task.smallestMissingNo(arr1, 0, n - 1));
		// Test B
		n = arr2.Length;
		Console.Write("\n " + task.smallestMissingNo(arr2, 0, n - 1));
		// Test C
		n = arr3.Length;
		Console.Write("\n " + task.smallestMissingNo(arr3, 0, n - 1));
	}
}

Output

 5
 4
 0
package main
import "fmt"
/*
    Go program for
    Find the smallest missing number in sorted array
*/

// Find a smallest missing number in distinct sorted array  
func smallestMissingNo(arr[] int, low int, high int) int {
	if low <= high {
		// Find middle position of given range
		var mid int = low + (high - low) / 2
		if arr[mid] == mid {
			// When mid index contains same value
			// Change range mid+1 to high
			return smallestMissingNo(arr, mid + 1, high)
		}
		// Change range low to mid-1
		return smallestMissingNo(arr, low, mid - 1)
	} else {
		// When low value is largest to high
		return low
	}
}
func main() {
	
	// Array of positive distinct elements
	var arr1 = [] int {0, 1, 2, 3, 4, 7, 11, 17}
	var arr2 = [] int {0, 1, 2, 3}
	var arr3 = [] int {1, 2, 3}
	// Test A
	var n int = len(arr1)
	fmt.Print("\n ", smallestMissingNo(arr1, 0, n - 1))
	// Test B
	n = len(arr2)
	fmt.Print("\n ", smallestMissingNo(arr2, 0, n - 1))
	// Test C
	n = len(arr3)
	fmt.Print("\n ", smallestMissingNo(arr3, 0, n - 1))
}

Output

 5
 4
 0
<?php
/*
    Php program for
    Find the smallest missing number in sorted array
*/
class MissingNumber
{
	// Find a smallest missing number in distinct sorted array  
	public	function smallestMissingNo($arr, $low, $high)
	{
		if ($low <= $high)
		{
			// Find middle position of given range
			$mid = $low + (int)(($high - $low) / 2);
			if ($arr[$mid] == $mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return $this->smallestMissingNo($arr, $mid + 1, $high);
			}
			// Change range low to mid-1
			return $this->smallestMissingNo($arr, $low, $mid - 1);
		}
		else
		{
			// When low value is largest to high
			return $low;
		}
	}
}

function main()
{
	$task = new MissingNumber();
	// Array of positive distinct elements
	$arr1 = array(0, 1, 2, 3, 4, 7, 11, 17);
	$arr2 = array(0, 1, 2, 3);
	$arr3 = array(1, 2, 3);
	// Test A
	$n = count($arr1);
	echo("\n ".$task->smallestMissingNo($arr1, 0, $n - 1));
	// Test B
	$n = count($arr2);
	echo("\n ".$task->smallestMissingNo($arr2, 0, $n - 1));
	// Test C
	$n = count($arr3);
	echo("\n ".$task->smallestMissingNo($arr3, 0, $n - 1));
}
main();

Output

 5
 4
 0
/*
    Node JS program for
    Find the smallest missing number in sorted array
*/
class MissingNumber
{
	// Find a smallest missing number in distinct sorted array  
	smallestMissingNo(arr, low, high)
	{
		if (low <= high)
		{
			// Find middle position of given range
			var mid = low + parseInt((high - low) / 2);
			if (arr[mid] == mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return this.smallestMissingNo(arr, mid + 1, high);
			}
			// Change range low to mid-1
			return this.smallestMissingNo(arr, low, mid - 1);
		}
		else
		{
			// When low value is largest to high
			return low;
		}
	}
}

function main()
{
	var task = new MissingNumber();
	// Array of positive distinct elements
	var arr1 = [0, 1, 2, 3, 4, 7, 11, 17];
	var arr2 = [0, 1, 2, 3];
	var arr3 = [1, 2, 3];
	// Test A
	var n = arr1.length;
	process.stdout.write("\n " + task.smallestMissingNo(arr1, 0, n - 1));
	// Test B
	n = arr2.length;
	process.stdout.write("\n " + task.smallestMissingNo(arr2, 0, n - 1));
	// Test C
	n = arr3.length;
	process.stdout.write("\n " + task.smallestMissingNo(arr3, 0, n - 1));
}
main();

Output

 5
 4
 0
#    Python 3 program for
#    Find the smallest missing number in sorted array
class MissingNumber :
	#  Find a smallest missing number in distinct sorted list  
	def smallestMissingNo(self, arr, low, high) :
		if (low <= high) :
			#  Find middle position of given range
			mid = low + int((high - low) / 2)
			if (arr[mid] == mid) :
				#  When mid index contains same value
				#  Change range mid+1 to high
				return self.smallestMissingNo(arr, mid + 1, high)
			
			#  Change range low to mid-1
			return self.smallestMissingNo(arr, low, mid - 1)
		else :
			#  When low value is largest to high
			return low
		
	

def main() :
	task = MissingNumber()
	#  Array of positive distinct elements
	arr1 = [0, 1, 2, 3, 4, 7, 11, 17]
	arr2 = [0, 1, 2, 3]
	arr3 = [1, 2, 3]
	#  Test A
	n = len(arr1)
	print("\n ", task.smallestMissingNo(arr1, 0, n - 1), end = "")
	#  Test B
	n = len(arr2)
	print("\n ", task.smallestMissingNo(arr2, 0, n - 1), end = "")
	#  Test C
	n = len(arr3)
	print("\n ", task.smallestMissingNo(arr3, 0, n - 1), end = "")

if __name__ == "__main__": main()

Output

  5
  4
  0
#    Ruby program for
#    Find the smallest missing number in sorted array
class MissingNumber 
	#  Find a smallest missing number in distinct sorted array  
	def smallestMissingNo(arr, low, high) 
		if (low <= high) 
			#  Find middle position of given range
			mid = low + (high - low) / 2
			if (arr[mid] == mid) 
				#  When mid index contains same value
				#  Change range mid+1 to high
				return self.smallestMissingNo(arr, mid + 1, high)
			end

			#  Change range low to mid-1
			return self.smallestMissingNo(arr, low, mid - 1)
		else
 
			#  When low value is largest to high
			return low
		end

	end

end

def main() 
	task = MissingNumber.new()
	#  Array of positive distinct elements
	arr1 = [0, 1, 2, 3, 4, 7, 11, 17]
	arr2 = [0, 1, 2, 3]
	arr3 = [1, 2, 3]
	#  Test A
	n = arr1.length
	print("\n ", task.smallestMissingNo(arr1, 0, n - 1))
	#  Test B
	n = arr2.length
	print("\n ", task.smallestMissingNo(arr2, 0, n - 1))
	#  Test C
	n = arr3.length
	print("\n ", task.smallestMissingNo(arr3, 0, n - 1))
end

main()

Output

 5
 4
 0
/*
    Scala program for
    Find the smallest missing number in sorted array
*/
class MissingNumber()
{
	// Find a smallest missing number in distinct sorted array  
	def smallestMissingNo(arr: Array[Int], low: Int, high: Int): Int = {
		if (low <= high)
		{
			// Find middle position of given range
			var mid: Int = low + (high - low) / 2;
			if (arr(mid) == mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return smallestMissingNo(arr, mid + 1, high);
			}
			// Change range low to mid-1
			return smallestMissingNo(arr, low, mid - 1);
		}
		else
		{
			// When low value is largest to high
			return low;
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: MissingNumber = new MissingNumber();
		// Array of positive distinct elements
		var arr1: Array[Int] = Array(0, 1, 2, 3, 4, 7, 11, 17);
		var arr2: Array[Int] = Array(0, 1, 2, 3);
		var arr3: Array[Int] = Array(1, 2, 3);
		// Test A
		var n: Int = arr1.length;
		print("\n " + task.smallestMissingNo(arr1, 0, n - 1));
		// Test B
		n = arr2.length;
		print("\n " + task.smallestMissingNo(arr2, 0, n - 1));
		// Test C
		n = arr3.length;
		print("\n " + task.smallestMissingNo(arr3, 0, n - 1));
	}
}

Output

 5
 4
 0
import Foundation;
/*
    Swift 4 program for
    Find the smallest missing number in sorted array
*/
class MissingNumber
{
	// Find a smallest missing number in distinct sorted array  
	func smallestMissingNo(_ arr: [Int], _ low: Int, _ high: Int) -> Int
	{
		if (low <= high)
		{
			// Find middle position of given range
			let mid: Int = low + (high - low) / 2;
			if (arr[mid] == mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return self.smallestMissingNo(arr, mid + 1, high);
			}
			// Change range low to mid-1
			return self.smallestMissingNo(arr, low, mid - 1);
		}
		else
		{
			// When low value is largest to high
			return low;
		}
	}
}
func main()
{
	let task: MissingNumber = MissingNumber();
	// Array of positive distinct elements
	let arr1: [Int] = [0, 1, 2, 3, 4, 7, 11, 17];
	let arr2: [Int] = [0, 1, 2, 3];
	let arr3: [Int] = [1, 2, 3];
	// Test A
	var n: Int = arr1.count;
	print("\n ", task.smallestMissingNo(arr1, 0, n - 1), terminator: "");
	// Test B
	n = arr2.count;
	print("\n ", task.smallestMissingNo(arr2, 0, n - 1), terminator: "");
	// Test C
	n = arr3.count;
	print("\n ", task.smallestMissingNo(arr3, 0, n - 1), terminator: "");
}
main();

Output

  5
  4
  0
/*
    Kotlin program for
    Find the smallest missing number in sorted array
*/
class MissingNumber
{
	// Find a smallest missing number in distinct sorted array  
	fun smallestMissingNo(arr: Array < Int > , low: Int, high: Int): Int
	{
		if (low <= high)
		{
			// Find middle position of given range
			val mid: Int = low + (high - low) / 2;
			if (arr[mid] == mid)
			{
				// When mid index contains same value
				// Change range mid+1 to high
				return this.smallestMissingNo(arr, mid + 1, high);
			}
			// Change range low to mid-1
			return this.smallestMissingNo(arr, low, mid - 1);
		}
		else
		{
			// When low value is largest to high
			return low;
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: MissingNumber = MissingNumber();
	// Array of positive distinct elements
	val arr1: Array < Int > = arrayOf(0, 1, 2, 3, 4, 7, 11, 17);
	val arr2: Array < Int > = arrayOf(0, 1, 2, 3);
	val arr3: Array < Int > = arrayOf(1, 2, 3);
	// Test A
	var n: Int = arr1.count();
	print("\n " + task.smallestMissingNo(arr1, 0, n - 1));
	// Test B
	n = arr2.count();
	print("\n " + task.smallestMissingNo(arr2, 0, n - 1));
	// Test C
	n = arr3.count();
	print("\n " + task.smallestMissingNo(arr3, 0, n - 1));
}

Output

 5
 4
 0
Last updated on by Kalkicode




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