Find the missing numbers in the given array-CodePudding

Implement a function which takes an array of numbers from 1 to 10 and returns the numbers from 1 to 10 which are missing. examples input: [5,2,6] output: [1,3,4,7,8,9,10]

C program for the above approach:

#include <bits/stdc  .h> 

using namespace std; 
 
// Function to find the missing elements 

void printMissingElements(int arr[], int N) 
{ 
 

    // Initialize diff 

    int diff = arr[0] - 0; 
 

    for (int i = 0; i < N; i  ) { 
 

        // Check if diff and arr[i]-i 

        // both are equal or not 

        if (arr[i] - i != diff) { 
 

            // Loop for consecutive 

            // missing elements 

            while (diff < arr[i] - i) { 

                cout << i   diff << " "; 

                diff  ; 

            } 

        } 

    } 
}

Driver Code

int main() 
{ 

    // Given array arr[] 

    int arr[] = { 5,2,6 }; 
 

    int N = sizeof(arr) / sizeof(int); 
 

    // Function Call 

    printMissingElements(arr, N); 

    return 0; 
}

How to solve this question for the given input?

CodePudding user response：

By this approach we are using space to reduce execution time. Here the time complexity is O(N) where N is the no of elements given in the array and space complexity is O(1) i.e 10' .

#include <bits/stdc  .h>

using namespace std;

void printMissingElements(int arr[], int n){
   
    // Using 1D dp to solve this
   
    int dp[11] = {0};
    for(int i = 0; i < n; i  ){
        dp[arr[i]] = 1;
    }
   
    // Traverse through dp list and check for
    // non set indexes
    for(int i = 1; i <= 10; i  ){
        if (dp[i] != 1) cout << i << " ";
    }
}

int main() {
    int arr[] = {6,7,11,10,13};
    int n = sizeof(arr) / sizeof(int);
    printMissingElements(arr, n);
}

CodePudding user response：

First of all "plzz" is not an English world. Second, the question is already there, no need to keep writing in comments "if anyone knows try to help me". Then learn standard headers:

CodePudding user response：

How about you sort your array before checking for missing elements like this and then add the following code in the printMissingElements function

void printMissingElements(int array[], int n, int low,
                  int high)
{
     std::sort(array, array   n);
    int* a = std::lower_bound(array, array   n, low);
    int lowerIndex = a - array;
    int i = lowerIndex, x = low ;
    while (i < n && x <= high) {
        if (array[i] != x)
            std::cout << x << " ";
        else
            i  ;
        x  ;
    }
    while (x <= high)
       std:: cout << x   << " ";
}

// Main program
int main()
{
    int array[] ={5,2,6};
    int n = sizeof(array) / sizeof(array[0]);
    int low = 1, high = 10;
    printMissingElements(array, n, low, high);
}