Find one duplicate in container with N+1 integers between 1 and N

Question

Time complexity is supposed to be \$O(n \cdot \log(n))\$ and space complexity is supposed to be \$O(1)\$. Neither the elements of the container nor the container should be modified.

// Copyright [2015] <none>
#include <cstdlib>
#include <cstddef>
#include <cassert>
#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
#include <random>
#include <algorithm>
#include <limits>

// #define NODEBUG

/**
 * Finds one duplicate number in container where the largest number in the
 * container is smaller than the size of the container.
 */
template <class It>
It FindOneDuplicate(It first, It last) {
  int n = static_cast<int>(std::distance(first, last) - 1);
  int range_start = 1;
  int range_end = n / 2;
  while (true) {
  next_range:
    int range_size = range_end - range_start + 1;
    int count = 0;
    for (auto current{first}; current != last; ++current) {
      int element = *current;
      if (element >= range_start && element <= range_end) {
        ++count;
        if (count > range_size) {
          n = range_end;
          range_end = (n + range_start) / 2;
          if (range_size == 1) {
            return current;
          }
          // break and continue
          goto next_range;
        }
      }
    }
    // This should never happen
    assert(range_end != n);

    range_start = range_end + 1;
    range_end = n;
  }
}

// This is just a test run
int main(int argc, char* argv[]) {
  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " <N>" << std::endl;
    return EXIT_FAILURE;
  }
  int n =
      static_cast<int>(std::strtol(argv[1], static_cast<char**>(nullptr), 10));
  assert(n > 0 && n < std::numeric_limits<int>::max());
  std::random_device rd;
  std::mt19937 generator(rd());
  std::uniform_int_distribution<> dist(1, n);
  std::size_t size{static_cast<std::size_t>(n + 1)};
  std::vector<int> elements(size);
  // Fill and increment except last
  std::iota(elements.begin(), elements.end() - 1, 1);
  // Fill last with random value [1..N]
  elements.back() = dist(generator);
  // Shuffle elements
  std::shuffle(elements.begin(), elements.end(), generator);
  auto duplicate = FindOneDuplicate(elements.begin(), elements.end());
  for (const auto& element : elements) {
    bool isduplicate = element == *duplicate;
    if (isduplicate) {
      // bold;red
      std::cout << "\033[1;31m";
    }
    std::cout << element;
    if (isduplicate) {
      // reset
      std::cout << "\033[0m";
    }
    if (&element != &elements.back()) {
      std::cout << ", ";
    }
  }
  std::cout << std::endl;
  return EXIT_SUCCESS;
}

Since this is my first real piece of C++ code I'd love to get some code review before I start working on any open source projects.

Note that I'm trying to follow the Google C++ style guide here.

Answer 1

Never use goto

There are times where you have a compelling reason to use goto. This really isn't one of them. Either make your function recursive, since it is in all but name. Or rewrite it to be iterative. Both of those would be preferred solutions. The reason I say this is because your logic is sort of logic a binary search, except the two different changes in range occur in different places and use different mechanisms. This makes it difficult to understand and, I imagine, debug.

A Better Algorithm

Add a helper function that will count the number of elements in your given range, breaking out early if you hit the amount you're going for:

template <typename It, typename V>
It find_if_extra(It first, It last, V start, V end)
{
    V count = 0;
    for (; first != last; ++first) {
        if (*first >= start && *first <= end) {
            ++count;
            if (count > end - start + 1) {
                return first;
            }
        }
    }

    return last;
}

This is basically the same thing you were doing in your loop, except substituting the return/goto pair for two returns. Now, we can just rewrite your original function to use this helper and the goto goes away:

template <class It>
It FindOneDuplicate(It first, It last) {
    using value_type = 
        typename std::iterator_traits<It>::value_type;

    value_type N = std::distance(first, last) - 1;
    value_type start = 1;
    value_type end = N/2;

    for (;;) {
        auto it = find_if_extra(first, last, start, end);

        if (it != last) {
            // recurse lower unless we're done
            if (start == end) {
                return it;
            }

            N = end;
            end = (N + start) / 2;
        }
        else {
            // recurse higher
            start = end + 1;
            end = N;
        }
    }
}

Assumptions on types

There's no reason to cast n to be an int. size_t is fine:

size_t n = std::distance(first, last) - 1;

Similarly, I would initialize element with auto. You take arbitrary iterators, what if we had a huge container of size_t? You'd overflow.

Also, avoid this construction:

auto current{first};

in favor of

auto current = first;

The former may change meaning in the future, and there's no reason to prefer it anyway.

Testing

Your test just outputs something to the screen. Ideally, you would write test that actually verify the behavior of your program.

Answer 2

1. I would still avoid direct-list-initialization (auto current{first};) at the moment, as the changed meaning just a short while ago (http://open-std.org/JTC1/SC22/WG21/docs/papers/2014/n3922.html) and not all compilers already implement the DR for C++14.

2. You should not use goto unless it makes the code significantly simpler. Yours doesn't cut it.

3. Your algo does successfully find the single duplicated element in a shuffled sequence of the first n positive integers.
   It also fulfills your performance-requirements, but it needs exactly that kind of input.

   You can easily achieve linear performance by just adding up all numbers and subtracting the sum of the sequence without the duplicate element (there's a simple closed form),
   or you can relax input-requirements and just find the first duplicate, by sorting and then using linear scanning to find duplicates.

4. You don't need an explicit flush, so avoid the overhead by not using std::endl.

5. return 0; at the end of main is implicit. No need to write it, or the less common return EXIT_SUCCESS;.

6. There's no advantage to avoiding copies of builtin types using references. Unless you really want to future-proof it for substituting an arbitrary-precision-type.

7. Your initialization of the PRNG isn't actually all that good, using just one unsigned int's worth of entropy. See Seed std::mt19937 from std::random_device for a better idea.

8. The assert in main is a really bad idea: You are using it to detect bad user-input, which isn't what it's for.

9. I wouldn't enclose an if-statements body in braces unless needed, and the Google C++ Style Guide gives you free choice there.

As an aside, the Google Style Guide has definite defects, a longer blog-article on that, which is kept current (4.45 now): Why Google Style Guide for C++ is a deal-breaker

Answer 3

Group/Order your header files

Having your headers organized correctly helps with readability, maintenance, and assists with preventing latent usage errors. The human mind is able to process ordered lists much faster than unsorted linear searching. By organizing your library #includes, ensuring that the proper files are included can be done quickly and safely. Group by local prototype/header, project libraries, non-standard libraries (Boost/QT), standard C++ libraries, and finally standard C libraries. Each group should be in lexicographical order.

Express Intent

Unless code is named or commented appropriately, the intent of your code may not be clear. In your function FindOneDuplicate, the iterator type used by your function must meet the requirements of a forward iterator (multi-passable). Express forward iterator in the signature and be sure to check that the iterator meets the requirement. The same applies to std::endl. If you do not intend to flush (whether the stream is buffered or not), then don’t call std::endl. If you did intend to flush, clarify that intent by avoiding std::endl and explicitly stating std::flush.

Beware of Overflow

Casting from an unsigned to a signed can result in unwanted behavior. Ensure that the converted value will not overflow.

Avoid goto

goto is an extremely powerful control structure that is better to be used for machine generated code. Code that utilizes goto often results in readability concerns and introduces errors in relation to the state of the system. You used goto to break from the for (), which is exactly what the less powerful break would have done. The flow control when a duplicate is not encountered is also confusing as you forced a single return point.

Prefer generic algorithms over tightly coupled functions

You can encourage code reuse and reduce code duplication by writing functions with generic programming in mind. Your FindOneDuplicate() function is tightly coupled with ints. If I wanted to find duplicates of a double, std::pair<>, etc, I would have to rewrite your function for the data type I wanted.

If you wanted to duplicate an element in a sequence in a generic fashion, randomly select an element from the sequence then push it on to the sequence. Distributions are cheap to construct.

template <typename FwdIt, typename RandomGenerator>
FwdIt select_randomly(FwdIt first, FwdIt last, RandomGenerator& rng) {
  if (first == last || std::next(first) == last) {
    return first;
  }
  std::uniform_int_distribution<> dist(0, std::distance(first, last) – 1);
  std::advance(first, dist(rng));
  return first;
}

Do not use assert() for error reporting/handling

Assertion failures are fatal to the entire process. Unexpected parameters that cause a function to fail should be handled appropriately.

Know your <algorithm>s

The sum-of-series approach illustrated by @Barry and @Deduplicator is a better solution for this specific problem. If you were looking for a generic algorithm to find duplicates in a sequence (not series), use the words of wisdom @Deduplicator recently shared, “If in doubt, sort”. The standard library provides algorithms for efficiently working on sorted sequences. You can find duplicates in a sorted sequence using std::adjacent_find().

Answer 4

Changelog:

1. Sorted & grouped headers
2. Using FwdIt
3. Using @Barry's approach to make stuff much cleaner
4. Moved some code out of main
5. assert the duplicate and then output to the user just for demonstration
6. Not checking user input at all because this is just a test run
7. Added comments to make it clear why I'm not just calculating a sum of all elements
8. Not flushing after line break
9. Not using brace initialization for now

-

// Copyright [2015] <none>
#include <cassert>
#include <cstddef>
#include <cstdlib>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <limits>
#include <numeric>
#include <random>
#include <vector>

// #define NODEBUG

template <class FwdIt,
          class T = typename std::iterator_traits<FwdIt>::value_type>
FwdIt FindIfLargerThanRange(FwdIt first, FwdIt last, T start, T end) {
  T count = 0;
  for (; first != last; ++first) {
    if (*first >= start && *first <= end) {
      ++count;
      if (count > end - start + 1) {
        break;
      }
    }
  }
  return first;
}

/**
 * Finds one duplicate number in container where the largest number in the
 * container is smaller than the size of the container.
 */
template <class FwdIt>
FwdIt FindOneDuplicate(FwdIt first, FwdIt last) {
  using value_type = typename std::iterator_traits<FwdIt>::value_type;
  value_type n = static_cast<value_type>(std::distance(first, last) - 1);
  value_type range_start = 1;
  value_type range_end = n / 2;
  FwdIt result;
  for (;;) {
    result = FindIfLargerThanRange(first, last, range_start, range_end);

    // If found
    if (result != last) {
      if (range_start == range_end) {
        break;
      }
      n = range_end;
      range_end = (n + range_start) / 2;
    } else {
      // This should never happen
      // If this happens there's an element >= size of container
      assert(range_end != n);

      range_start = range_end + 1;
      range_end = n;
    }
  }
  return result;
}

/*
 * Note that this is really only a test! FindOneDuplicate can not assume that
 * all numbers from 1 to N are in the container nor can it assume that there's
 * only one duplicate in the container.
 */
template <class FwdIt,
          class T = typename std::iterator_traits<FwdIt>::value_type>
T FillWithOneDuplicate(FwdIt first, FwdIt last) {
  T n = static_cast<T>(std::distance(first, last) - 1);
  std::random_device rd;
  std::mt19937 generator(rd());
  std::uniform_int_distribution<T> dist(1, n);
  T secret_number = dist(generator);
  // Fill and increment except last
  std::iota(first, last - 1, 1);
  // Fill last with random value [1..N]
  *(last - 1) = secret_number;
  // Shuffle elements
  std::shuffle(first, last, generator);
  return secret_number;
}

template <class FwdIt>
void PrintDuplicate(FwdIt first, FwdIt last, FwdIt duplicate) {
  for (bool has_next = first != last; has_next;) {
    if (*first == *duplicate) {
      // bold;red -> duplicate -> reset
      std::cout << "\033[1;31m" << *duplicate << "\033[0m";
    } else {
      std::cout << *first;
    }
    ++first;
    has_next = first != last;
    if (has_next) {
      std::cout << ", ";
    }
  }
  std::cout << '\n';
}

// Test run
int main(int argc, char* argv[]) {
  if (argc != 2) {
    std::cerr << "Usage: " << argv[0] << " <N>\n";
    return EXIT_FAILURE;
  }
  // Note that if n is too large a bad alloc might be thrown depending on the
  // system I guess.
  // Furthermore this may also overflow if the type of the vector can not store
  // the value n.
  std::size_t n = std::strtoull(argv[1], static_cast<char**>(nullptr), 10);
  std::vector<std::size_t> elements(n + 1);
  auto secret_number = FillWithOneDuplicate(elements.begin(), elements.end());
  auto duplicate = FindOneDuplicate(elements.begin(), elements.end());
  assert(secret_number == *duplicate);
  // Output to the user to demonstrate that it really works
  PrintDuplicate(elements.begin(), elements.end(), duplicate);
  return EXIT_SUCCESS;
}