6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Nov 23 '15 at 13:26
  • \$\begingroup\$ The question is still unclear from this post alone. There is no mention that there may be more than one repeated number - and thus all numbers \$1\$ to \$N\$ may not be represented in the list. Based on this post alone summing up every number and subtracting it from \$n(n+1)/2\$ would be the most efficient solution. Even still I was about to highlight an \$O(n)\$ algorithm until I noticed the last edit specified that "the elements of the container should not be modified" which I assume also means the container itself should not be modified (no shuffling, sorting, etc). \$\endgroup\$ – twohundredping Nov 24 '15 at 23:16
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Regarding auto x{y}; sometime in the future changing meaning: He depends on the new (corrected) semantics, otherwise the code would be ill-formed. \$\endgroup\$ – Deduplicator Nov 23 '15 at 4:29
  • 1
    \$\begingroup\$ As for the sum idea: I don't think it's given that all integers 1..N are present. Nothing is given about the values except that they are all between 1 and N. \$\endgroup\$ – RemcoGerlich Nov 23 '15 at 9:16
  • \$\begingroup\$ std::distance gives me difference_type and not size_t so why can I assume size_t to be safe here? Furthermore I would implicitly cast when I use it later on and I don't want to implicitly cast right? @RemcoGerlich is absolutely right the test I did is probably not that good. But great approach if that were the case though @Barry. \$\endgroup\$ – noob Nov 23 '15 at 12:31
  • \$\begingroup\$ Furthermore I just tried to use std::accumulate but I'll have to break early and I don't thing I can do that in std::accumulate so therefore I think I'm better off with the loop I got. \$\endgroup\$ – noob Nov 23 '15 at 12:50
  • \$\begingroup\$ @mash Changed my answer based on misunderstanding of the problem. \$\endgroup\$ – Barry Nov 23 '15 at 14:24
5
\$\begingroup\$
  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

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 7 seems interesting but I guess it doesn't matter in this case. What makes return 0; better than return EXIT_SUCCESS; I recently saw a bug where someone did a return 1 and then moved the code in another function outside of main which then did not exit because 1 was a valid return for that function. With EXIT_FAILURE that bug would've been much easier to spot. \$\endgroup\$ – noob Nov 23 '15 at 14:07
  • \$\begingroup\$ EXIT_SUCCESS and EXIT_FAILURE are implementation defined numeric expressions for returning success or failure to the operating system. They are used in writing portable code because there are operating systems that use values besides 0/1 for success and failure. \$\endgroup\$ – Snowhawk Nov 23 '15 at 23:03
  • \$\begingroup\$ @Snowhawk04: Yes, they are for portability. But 0 is also for a successful exit, so one can use that portably. And I didn't suggest removing EXIT_FAILURE. \$\endgroup\$ – Deduplicator Nov 24 '15 at 0:18
2
\$\begingroup\$

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().

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ But if I'd sort and then use something like std::adjacent_find I would not have O(n * log n) time complexity anymore. \$\endgroup\$ – noob Nov 23 '15 at 14:56
  • \$\begingroup\$ For std::sort, the complexity is O(N·log(N)), where N = std::distance(first, last) comparisons. (since C++11). For std::adjacent_find, the complexity is linear. Both fit within your complexity requirement of O(N log N). \$\endgroup\$ – Snowhawk Nov 23 '15 at 21:59
  • \$\begingroup\$ But sort will swap and with my current implementation I won't need to modify the container at all nor do I need to copy the container so it'll definitely be more awesome than sorting right. Furthermore yes you're right it'll be the same big-O complexity but with sort you'll actually get: Θ(n * log n) and I could get Ω(n) with my current solution if I'm not mistaken. In other words I'll definitely not throw my solution away if it's that much better than sort. \$\endgroup\$ – noob Nov 23 '15 at 22:53
  • \$\begingroup\$ There are other generic approaches that exist that will work in O(n log n) time without requiring sorting or O(1) space. Also, your solution is nowhere near linear when the duplicate elements exist at the end of a sequence (e.g. elements = {1, 2, 3, 4, 5, 6, 6}). \$\endgroup\$ – Snowhawk Nov 23 '15 at 23:50
  • \$\begingroup\$ Well yeah that list of elements would require four iterations. Also what other generic approaches exist? \$\endgroup\$ – noob Nov 24 '15 at 6:55
1
\$\begingroup\$

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;
}
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.