There is a sequence of different int numbers. You must efficiently find any int number that is different from the data. We believe that such a number exists.

  • For a sequence about which nothing is more known, there is not and there can be no algorithm more efficient than O(n) . The algorithms for O(n) are trivial. A natural question arises: what kind of "efficiency" did the author expect? And if we are talking about O(n) , then why do we need a spec? - AnT

1 answer 1

Find the maximum, add 1. O(n) .

 int x = max_element(begin(array),end(array));

Minus - it is theoretically possible that the array has at the same time the minimum / maximum representable values ​​...

If the structure is sorted, we immediately look at the minimum / maximum values, if they are not the minimum / maximum representable, we take 1 less (respectively, more), total - O(1) .

If they are the minimum / maximum representable - go to the first "lumen", take it. O(n) .

In general, less than O(n) I do not see options ...

  • ... and get an overflow. - Vlad from Moscow
  • Generally speaking, data can be thrown into any structure, not just an array, so logn is desirable - generator
  • See addition to answer. - Harry
  • @generator: The “throwing” itself will take O(n) .. O(n log n) time. Meaning? - AnT
  • The @AnT data representation is not included in the algorithm, it is given "as is" in a convenient structure, i.e. the complexity of adding can be ignored - generator