fork download
copy 
  1. /* CPP program to find the smallest  
  2.   positive missing number */
  3. #include <bits/stdc++.h> 
  4. using namespace std; 
  5.  
  6. // Function to find smallest positive 
  7. // missing number. 
  8. int findMissingNo(int arr[], int n) 
  9. { 
  10.     // to store current array element 
  11.     int val; 
  12.  
  13.     // to store next array element in 
  14.     // current traversal 
  15.     int nextval; 
  16.  
  17.     for (int i = 0; i < n; i++) { 
  18.  
  19.         // if value is negative or greater 
  20.         // than array size, then it cannot 
  21.         // be marked in array. So move to 
  22.         // next element. 
  23.         if (arr[i] <= 0 || arr[i] > n) 
  24.             continue; 
  25.  
  26.         val = arr[i]; 
  27.  
  28.         // traverse the array until we 
  29.         // reach at an element which 
  30.         // is already marked or which 
  31.         // could not be marked. 
  32.         while (arr[val - 1] != val) { 
  33.             nextval = arr[val - 1]; 
  34.             arr[val - 1] = val; 
  35.             val = nextval; 
  36.             if (val <= 0 || val > n) 
  37.                 break; 
  38.         } 
  39.     } 
  40.  
  41.     // find first array index which is 
  42.     // not marked which is also the 
  43.     // smallest positive missing 
  44.     // number. 
  45.     for (int i = 0; i < n; i++) { 
  46.         if (arr[i] != i + 1) { 
  47.             return i + 1; 
  48.         } 
  49.     } 
  50.  
  51.     // if all indices are marked, then 
  52.     // smallest missing positive 
  53.     // number is array_size + 1. 
  54.     return n + 1; 
  55. } 
  56.  
  57. // Driver code 
  58. int main() 
  59. { 
  60.     int arr[] = { 2, 3, 7, 6, 8, -1, -10, 15,1 }; 
  61.     int arr_size = sizeof(arr) / sizeof(arr[0]); 
  62.     int missing = findMissingNo(arr, arr_size); 
  63.     for(int i=0;i<arr_size;i++){
  64.     	cout<<arr[i]<<" ";
  65.     }
  66.     cout<<endl;
  67.     cout << "The smallest positive missing number is"<<missing;
  68. }
  69.  
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 6 8 6 7 8 1 
The smallest positive missing number is4
https://ideone.com/Z01Ut4
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!