Find missing elements from an array
The problem of finding missing elements in a sorted array is a common programming task. Given an array that is sorted in ascending order and may contain duplicate elements, the goal is to identify and display the missing elements in the sequence. This task can be approached using a simple algorithm that iterates through the array and identifies gaps between consecutive elements.
Problem Statement
You are given a sorted array of integers that may contain duplicates. Your task is to find and display the missing
elements in the sequence. For example, if the input array is [1, 2, 3, 4, 4, 7, 7]
, the missing
elements are 5 and 6.
Solution Approach
To solve this problem, we can iterate through the sorted array and for each pair of consecutive elements
arr[i]
and arr[i+1]
, we check for the missing elements in the range
(arr[i] + 1)
to (arr[i+1] - 1)
. If the difference between arr[i+1]
and
arr[i]
is greater than 1, then there are missing elements in between.
Pseudocode
class MyArray:
method find_missing(arr, size):
for i from 0 to size - 2:
for j from (arr[i] + 1) to (arr[i + 1] - 1):
print j
Algorithm Explanation
- Create a class
MyArray
to encapsulate the array manipulation logic. - In the
find_missing
method, iterate through the array usingi
from 0 tosize - 2
. This loop goes up to the second-to-last element of the array to ensure that we can accessarr[i+1]
. - Inside the first loop, use another loop with variable
j
ranging from(arr[i] + 1)
to(arr[i + 1] - 1)
. This loop iterates through the range between consecutive elements to find the missing elements. - Print the value of
j
, which represents the missing element in the sequence. - The loops will automatically handle duplicate elements and only consider the gaps between unique consecutive elements.
Example
Let's take the input array [1, 2, 3, 4, 4, 7, 7]
as an example to demonstrate the algorithm.
-
For
i = 0
,arr[i] = 1
andarr[i + 1] = 2
:- The loop for
j
runs from2
to1
, but there are no missing elements. So, no output for this iteration.
- The loop for
-
For
i = 1
,arr[i] = 2
andarr[i + 1] = 3
:- The loop for
j
runs from3
to2
, and the missing element is2
.
- The loop for
-
For
i = 2
,arr[i] = 3
andarr[i + 1] = 4
:- The loop for
j
runs from4
to3
, and the missing element is3
.
- The loop for
-
For
i = 3
,arr[i] = 4
andarr[i + 1] = 4
:- The loop for
j
doesn't run since there's no gap between the same element.
- The loop for
-
For
i = 4
,arr[i] = 4
andarr[i + 1] = 7
:- The loop for
j
runs from5
to6
, and the missing elements are5
and6
.
- The loop for
-
For
i = 5
,arr[i] = 7
andarr[i + 1] = 7
:- The loop for
j
doesn't run since there's no gap between the same element.
- The loop for
Code Solution
/*
C++ Program
Find missing elements from an array
*/
#include<iostream>
using namespace std;
class MyArray {
public:
//Find all missing element in given sorted array
void find_missing(int arr[], int size) {
if (size <= 1) {
return;
} else {
for (int i = 0; i < size - 1; ++i) {
//Find the all missing elements
for (int j = arr[i] + 1; j < arr[i + 1]; ++j) {
//display missing element
cout << " " << j;
}
}
}
}
};
int main() {
MyArray obj ;
int arr[] = {
1,
2,
3,
4,
4,
7,
7
};
//Get the size of array
int size = sizeof(arr) / sizeof(arr[0]);
obj.find_missing(arr, size);
return 0;
}
Output
5 6
/*
Java Program
Find missing elements from an array
*/
public class MyArray
{
//Find all missing element in given sorted array
public void find_missing(int []arr,int size)
{
if(size<=1)
{
return;
}
else
{
for (int i = 0; i < size-1; ++i)
{
//Find the all missing elements
for (int j = arr[i]+1; j < arr[i+1]; ++j)
{
//display missing element
System.out.print(" "+j);
}
}
}
}
public static void main(String[] args) {
MyArray obj = new MyArray();
//Define the value of array elements
int []arr = {1, 2, 3, 4, 4, 7, 7} ;
//Get the size of array
int size = arr.length;
obj.find_missing(arr,size);
}
}
Output
5 6
/*
C# Program
Find missing elements from an array
*/
using System;
public class MyArray {
//Find all missing element in given sorted array
public void find_missing(int[] arr, int size) {
if (size <= 1) {
return;
} else {
for (int i = 0; i < size - 1; ++i) {
//Find the all missing elements
for (int j = arr[i] + 1; j < arr[i + 1]; ++j) {
Console.Write(" " + j);
}
}
}
}
public static void Main(String[] args) {
MyArray obj = new MyArray();
//Define the value of array elements
int[] arr = {
1,
2,
3,
4,
4,
7,
7
};
//Get the size of array
int size = arr.Length;
obj.find_missing(arr, size);
}
}
Output
5 6
<?php
/*
Php Program
Find missing elements from an array
*/
class MyArray {
//Find all missing element in given sorted array
public function find_missing($arr, $size) {
if ($size <= 1) {
return;
} else {
for ($i = 0; $i < $size - 1; ++$i) {
//Find the all missing elements
for ($j = $arr[$i] + 1; $j < $arr[$i + 1]; ++$j) {
//display missing element
echo(" ". $j);
}
}
}
}
}
function main() {
$obj = new MyArray();
//Define the value of array elements
$arr = array(1, 2, 3, 4, 4, 7, 7);
//Get the size of array
$size = count($arr);
$obj->find_missing($arr, $size);
}
main();
Output
5 6
/*
Node Js Program
Find missing elements from an array
*/
class MyArray {
//Find all missing element in given sorted array
find_missing(arr, size) {
if (size <= 1) {
return;
} else {
for (var i = 0; i < size - 1; ++i) {
//Find the all missing elements
for (var j = arr[i] + 1; j < arr[i + 1]; ++j) {
//display missing element
process.stdout.write(" " + j);
}
}
}
}
}
function main(args) {
var obj = new MyArray();
//Define the value of array elements
var arr = [1, 2, 3, 4, 4, 7, 7];
//Get the size of array
var size = arr.length;
obj.find_missing(arr, size);
}
main();
Output
5 6
# Python 3 Program
# Find missing elements from an array
class MyArray :
# Find all missing element in given sorted array
def find_missing(self, arr, size) :
if (size <= 1) :
return
else :
i = 0
while (i < size - 1) :
# Find the all missing elements
j = arr[i] + 1
while (j < arr[i + 1]) :
print(" ", j, end = "")
j += 1
i += 1
def main() :
obj = MyArray()
arr = [1, 2, 3, 4, 4, 7, 7]
size = len(arr)
obj.find_missing(arr, size)
if __name__ == "__main__":
main()
Output
5 6
# Ruby Program
# Find missing elements from an array
class MyArray
# Find all missing element in given sorted array
def find_missing(arr, size)
if (size <= 1)
return
else
i = 0
while (i < size - 1)
# Find the all missing elements
j = arr[i] + 1
while (j < arr[i + 1])
print(" ", j)
j += 1
end
i += 1
end
end
end
end
def main()
obj = MyArray.new()
arr = [1, 2, 3, 4, 4, 7, 7]
size = arr.length
obj.find_missing(arr, size)
end
main()
Output
5 6
/*
Scala Program
Find missing elements from an array
*/
class MyArray {
//Find all missing element in given sorted array
def find_missing(arr: Array[Int], size: Int): Unit = {
if (size <= 1) {
return;
} else {
var i: Int = 0;
while (i < size - 1) {
//Find the all missing elements
var j: Int = arr(i) + 1;
while (j < arr(i + 1)) {
print(" " + j);
j += 1;
}
i += 1;
}
}
}
}
object Main {
def main(args: Array[String]): Unit = {
val obj: MyArray = new MyArray();
val arr: Array[Int] = Array(1, 2, 3, 4, 4, 7, 7);
val size: Int = arr.length;
obj.find_missing(arr, size);
}
}
Output
5 6
/*
Swift Program
Find missing elements from an array
*/
class MyArray {
//Find all missing element in given sorted array
func find_missing(_ arr: [Int], _ size: Int) {
if (size <= 1) {
return;
} else {
var i: Int = 0;
while (i < size - 1) {
//Find the all missing elements
var j: Int = arr[i] + 1;
while (j < arr[i + 1]) {
print(" ", j, terminator: "");
j += 1;
}
i += 1;
}
}
}
}
func main() {
let obj: MyArray = MyArray();
let arr: [Int] = [1, 2, 3, 4, 4, 7, 7];
let size: Int = arr.count;
obj.find_missing(arr, size);
}
main();
Output
5 6
//C Program
//Find missing elements from an array
#include <stdio.h>
//Find all missing element in given sorted array
void find_missing(int arr[],int size)
{
if(size<=1)
{
return;
}
else
{
for (int i = 0; i < size-1; ++i)
{
//Find the all missing elements
for (int j = arr[i]+1; j < arr[i+1]; ++j)
{
//display missing element
printf(" %d\n",j);
}
}
}
}
int main()
{
//Define the value of array elements
int arr[] ={1, 2, 3, 4, 4, 7, 7} ;
//Get the size of array
int size=sizeof(arr) / sizeof(arr[0]);
find_missing(arr,size);
return 0;
}
Output
5
6
Time Complexity
Let n
be the size of the input array.
- The outer loop runs
n-1
times. - The inner loop can potentially run up to
n-1
times in total (when all elements are consecutive). - Therefore, the time complexity of the algorithm is O(n).
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