# 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

1. Create a class `MyArray` to encapsulate the array manipulation logic.
2. In the `find_missing` method, iterate through the array using `i` from 0 to `size - 2`. This loop goes up to the second-to-last element of the array to ensure that we can access `arr[i+1]`.
3. 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.
4. Print the value of `j`, which represents the missing element in the sequence.
5. 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.

1. For `i = 0`, `arr[i] = 1` and `arr[i + 1] = 2`:

• The loop for `j` runs from `2` to `1`, but there are no missing elements. So, no output for this iteration.
2. For `i = 1`, `arr[i] = 2` and `arr[i + 1] = 3`:

• The loop for `j` runs from `3` to `2`, and the missing element is `2`.
3. For `i = 2`, `arr[i] = 3` and `arr[i + 1] = 4`:

• The loop for `j` runs from `4` to `3`, and the missing element is `3`.
4. For `i = 3`, `arr[i] = 4` and `arr[i + 1] = 4`:

• The loop for `j` doesn't run since there's no gap between the same element.
5. For `i = 4`, `arr[i] = 4` and `arr[i + 1] = 7`:

• The loop for `j` runs from `5` to `6`, and the missing elements are `5` and `6`.
6. For `i = 5`, `arr[i] = 7` and `arr[i + 1] = 7`:

• The loop for `j` doesn't run since there's no gap between the same element.

## 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);
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);

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).

## 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.