-2

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?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Saiteja
  • 3
  • 5
  • The numbers in your input `arr` are not from 1 to 10, as the requirement states. – paolo May 26 '22 at 08:11
  • Plzz help me@paolo c++ code... Tell me the right code for the given input – Saiteja May 26 '22 at 08:15
  • The input need not be sorted. The simplest solution here would be to create a set of numbers iterating through the input array once and then going from 1 to 10 print all the numbers not in the set. A `bool[10]` array can be used instead of a real set here... – fabian May 26 '22 at 09:45
  • 2
    Also obligatory [no `#include ` please](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), especially not in combination with `using namespace std;` – fabian May 26 '22 at 09:59

4 Answers4

1

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: Why should I not #include <bits/stdc++.h>? Then learn Why is "using namespace std;" considered bad practice?

Then read the text of the problem: "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]"

You need to "return the numbers from 1 to 10 which are missing." I suggest that you really use C++ and get std::vector into your toolbox. Then you can leverage algorithms and std::find is ready for you.

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
std::vector<int> missingElements(const std::vector<int> v) 
{ 
    std::vector<int> missing;
    for (int i = 1; i <= 10; ++i) {
        if (find(v.begin(), v.end(), i) == v.end()) {
            missing.push_back(i);
        }
    }
    return missing;
}
 
int main() 
{
    std::vector<int> arr = { 5, 2, 6 }; 
    std::vector<int> m = missingElements(arr); 
    copy(m.begin(), m.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    return 0; 
}

If you want to do something with lower computational complexity you can have an already filled vector and then mark for removal the elements found. Then it's a good chance to learn the erase–remove idiom:

std::vector<int> missingElements(const std::vector<int> v) 
{ 
    std::vector<int> m = { -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    for (const auto& x: v) {
        m[x] = -1;
    }
    m.erase(remove(m.begin(), m.end(), -1), m.end());
    return m;
}
Costantino Grana
  • 3,132
  • 1
  • 15
  • 35
  • @Saiteja The accepted answer is wrong. It requires more work for fixing. – Costantino Grana May 26 '22 at 10:49
  • Sir, you are right but this solution is also acceptable for arrays where non-repeated elements are present. However, for your given array there is another solution possible. I have just posted it. Kindly, go through it, – Sowaiba9801 May 26 '22 at 11:24
0

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<iostream>


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) std::cout << i << " ";
    }
}

int main() {
    int arr[] = {5,2,6};
    int n = sizeof(arr) / sizeof(int);
    printMissingElements(arr, n);
}
Sourav Dutta
  • 145
  • 8
  • Notice how the example array doesn't respect the problem requirements and is causing UB. – Costantino Grana May 26 '22 at 12:57
  • Again [Why should I not #include ?](https://stackoverflow.com/q/31816095/6070341) and [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/6070341) – Costantino Grana May 26 '22 at 12:58
  • 1. Approach is independent of order of inputs so for a given set of inputs in any order will give the same result. and i have changed the input array as per the question. – Sourav Dutta May 30 '22 at 18:24
  • 2. It is basically a header file that includes every standard library. In programming contests, using this file is a good idea, when you want to reduce the time wasted. Only thing to take care is if you try to compile your code with some compiler other than GCC it might fail; e.g. MSVC do not have this header. When we import a namespace we are essentially pulling all type definitions into the current scope. The std namespace is huge. But for codes with small logical implementation it will be easier to use namespace as std @CostantinoGrana – Sourav Dutta May 31 '22 at 05:49
0
    void printMissingElements(int arr[], int n,int low, int high)
{
    bool range[high - low + 1] = { false };

    for (int i = 0; i < n; i++) {
        if (low <= arr[i] && arr[i] <= high)
            range[arr[i] - low] = true;
    }
    for (int x = 0; x <= high - low; x++) {
        if (range[x] == false)
           std:: cout << low + x << " ";
    }
}
int main()
{
    int arr[] = { 5,2,6,6,6,6,8,10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 1, high = 10;
    printMissingElements(arr, n, low, high);
    return 0;
}

Output

Sowaiba9801
  • 81
  • 7
0

I think this will work:

vector<int> missingnumbers(vector<int> A, int N)
{ vector<int> v;
  for(int i=1;i<=10;i++)
    v.push_back(i);
  sort(A.begin(),A.end());
  int j=0;
  while(j<v.size()) {
  if(binary_search(A.begin(),A.end(),v[j]))
    v.erase(v.begin()+j);
    else
    j++;
  }
 return v;
}
Vaibhav Vishal Singh
  • 123
  • 7