Find the minimum positive integer (positive, integer, greater than 0 ) that is not in the original array A

For example:

For A = [1, 3] answer: 2

For A = [1, 4, 6, 1, 3, 2] answer is: 5

  • Sort the array and in one pass find the answer. - Akina
  • I do that, but something's not working out yet. Could you tell me how to do it? - Cool_Dude
  • What does not work- sort? - MBo
  • Mutually exclusive paragraphs: "find a number in this array that is not in this array"? Correct the condition. - slippyk
  • The condition is find in the array the minimum number that is not in the array. For example A {1, 3} - Answer: 2. - Cool_Dude

4 answers 4

My compact and beautiful solution without unnecessary sorting

 int mas[] = {1, -1, 7, 0, 1, 2, 4}; int length = sizeof(mas) / sizeof(mas[0]); int res = 1; for (int j = 0; j < length; j++) for (int i = 0; i < length; i++) { if (mas[i] == res) { res++; break; } } cout<<res;
  • Thanks for the answer. Well, I did not understand, the first cycle, why is it needed? - Cool_Dude
  • your compact and beautiful solution will not work correctly - AR Hovsepyan
  • one
    Compact, beautiful, slow solution, but without unnecessary sorting! - int3
  • one
    @ARHovsepyan I do not know who deleted the comment. I don’t remember rudeness there, just the facts: you are without proof (without reason called the answer wrong), while having your broken answer to the same question (the result is that the correct answer is minus, and the wrong one is sabotage). I think this is meanness. If this comment is deleted by someone. Write ¶ No need to space after the \ @ put that in kindergarten. - jfs
  • one
    The comment has been and has been deleted. Apparently, it was automatically deleted by the system after putting a flag on it because of the coincidence of some word from it with a list of "bad" words that Nicholas added to some sort of automatic deletion script. - Yuriy SPb ♦

C++ not a writer, but I can offer two options:

Baseline :

 int a[ 6 ] = { 1, 4, 6, 1, 3, 2 }; int size = sizeof( a ) / sizeof( a[ 0 ] );

Option 1:

because By the condition the number must be greater than 0 , then starting from 1 check all the numbers that are not included in the array. The first will be that.

 int min = 1; while (true) { bool isContain = false; for (int i = 0; i < size; i++) { if (min == a[ i ]) { isContain = true; break; } } if (isContain) { min++; } else { std::cout << min << "\n"; break; } }

Option 2:

First, we sort the original array (in ascending order in this case), and check the difference of neighboring elements. If we get:

  • 0 - elements are equal;
  • 1 - elements go in order;
  • 2 or more means that the minimum element is in this range.

We add 1 to the element that is to the left in the pair - this value will be minimal.

 for (int j = 1; j < size; j++) { for (int i = 0; i < size - j; i++) { if (a[ i ] > a[ i + 1 ]) { int b = a[ i ]; a[ i ] = a[ i + 1 ]; a[ i + 1 ] = b; } } } for (int i = 1; i < size; i++) { if (a[ i ] - a[ i - 1 ] > 1) { std::cout << a[ i - 1 ] + 1 << "\n"; break; } }
  • It is not clear why the quadratic sorting algorithm should be used. As is the second option does not work. For a[] = {-1}; expected: 1 output, but nothing output - jfs

take the number n = 1 ; Look in the array for this number. If it is, then ++n ; and repeat the loop until it is in the array of such a number.

Or sort the array, and let's say it has a size of 10 :

 const int sz = 10; int m[10]; // инициализация, потом сортировка int k = 1; for (int i = 0; i < sz; ++i) { if ( m[i] == k ) { if (m[i] == m[i +1]) continue; ++k; } else { cout << "это число: " << k; break; } }
  • the solution does not work for int m[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 1}; . Expected output: 2 . Your code displays: это число: 1 . - jfs
  • I did not say that I wrote a beautiful code, which takes into account all the circumstances. I don’t have to do that, because I just offer an option and don’t test and maintain it, and then I pass the code for review, I don’t write code for anyone. - AR Hovsepyan
  • wrong decision. And here is the beauty. The answer is simply wrong - jfs

Linear algorithm:

  1. Mark all numbers in the interval [1, n] that are in the input array, where n is the size of the array
  2. find the first unmarked number.
 #include <algorithm> #include <iostream> #include <iterator> #include <vector> int main() { // read numbers std::istream_iterator<int> numbers {std::cin}, eof; std::vector<int> arr(numbers, eof); // mark numbers in [1, n] range that are in the array size_t n = arr.size(); std::vector<bool> m(n+1, false); for (int x : arr) if (1 <= x && x <= n) m[x-1] = true; // find the first absent number (position + 1) auto it = std::find(std::begin(m), std::end(m), false); std::cout << (std::distance(std::begin(m), it) + 1) << std::endl; }

An example .

  • vectors and other containers were not discussed, the question concerned arrays - AR Hovsepyan
  • no need to invent. There are no restrictions on the use of the vector in question. In the example, the input is read from the standard input, from a static array it would be even easier to take the input ¶ The fact that I indicated to your mistake in your decision that it doesn’t work does not mean that you have other correct working answers (click the link in the answer ) you need to put cons. I see someone else was not too lazy to deliver a minus answer two years ago. Petty dirty guy however caught. - jfs
  • I wanted to say steps, not memory - AR Hovsepyan