Find the missing number in a given integer array of 1 to 100

Find the missing element from the given Array. 

Example

Input: arr={ 1, 2, 3, 8, 12 }
Output: missing[]=[4, 5, 6, 7, 9, 10, 11]

Approach

Java

import java.util.Arrays;

public class FindMissingNumber1toN {

    public static void main(String[] args) {

        int arr[] = { 1, 2, 3, 8, 12 };

        int missing[] = findMissing(arr);

        System.out.println(Arrays.toString(missing));

    }

    // find missing element

    private static int[] findMissing(int[] arr) {

        int max = maxElement(arr);

        // if no missing

        if (max == arr.length)

            return null;

        int miss[] = new int[max - arr.length];

        // assume all are missing

        boolean missing[] = new boolean[max + 1];

        // iterate till end of arr

        for (int i = 0; i < arr.length; i++) {

            // update non-missing element

            missing[arr[i]] = true;

        }

        int index = 0;

        for (int i = 1; i < missing.length; i++) {

            if (!missing[i]) {

                miss[index++] = i;

            }

        }

        return miss;

    }

    // find maximum element

    private static int maxElement(int[] arr) {

        int max = arr[0];

        for (int i = 1; i < arr.length; i++) {

            if (arr[i] > max)

                max = arr[i];

        }

        return max;

    }

}

C++

#include <bits/stdc++.h>

using namespace std;

// find maximum element

int maxElement(int arr[],int n)

{

    int max = arr[0];

    for (int i = 1; i <n; i++) 

      {

            if (arr[i] > max)

                max = arr[i];

     }

        return max;

}

    // find missing element

vector<int> findMissing(int arr[],int n) 

{

    vector<int> missing;

    int max = maxElement(arr,n);

    // if no missing

    if (max ==n)

     return missing;

   // assume all are missing

    bool miss[max+1];

    memset(miss,false,sizeof(miss));

        // iterate till end of arr

    for (int i = 0; i <n; i++) {

            // update non-missing element

            miss[arr[i]] = true;

        }

    int index = 0;

        for (int i = 1; i <=max; i++) {

            if (!miss[i]) {

            missing.push_back(i);

            }

        }

        return missing;

}

int main()

{

  int arr[] = { 1, 2, 3, 8, 12 };

  int n=sizeof(arr)/sizeof(arr[0]);

  vector<int> missing = findMissing(arr,n);

  for(int i=0;i<missing.size();i++)

     cout<<missing[i]<<" ";

  return 0;

}