Erez Shmiel Erez Shmiel - 3 months ago 8
C++ Question

Is there any number repeated in the array?

There's array of size n. The values can be between 0 and (n-1) as the indices.

For example:

array[4] = {0, 2, 1, 3}


I should say if there's any number that is repeated more than 1 time.

For example:
array[5] = {3,4,1,2,4}
-> return
true
because 4 is repeated.

This question has so many different solutions and I would like to know if this specific solution is alright (if yes, please prove, else refute).

My solution (let's look at the next example):

array: indices 0 1 2 3 4
values 3 4 1 2 0


So I suggest:


  1. count the sum of the indices (4x5 / 2 = 10) and check that the values' sum (3+4+1+2+0) is equal to this sum. if not, there's repeated number.

  2. in addition to the first condition, get the multiplication of the indices(except 0. so: 1x2x3x4) and check if it's equal to the values' multiplication (except 0, so: 3x4x1x2x0).

    => if in each condition, it's equal then I say that there is NO repeated number. otherwise, there IS a repeated number.



Is it correct? if yes, please prove it or show me a link. else, please refute it.

Answer

Why your algorithm is wrong?

Your solution is wrong, here is a counter example (there may be simpler ones, but I found this one quite quickly):

int arr[13] = {1, 1, 2, 3, 4, 10, 6, 7, 8, 9, 10, 11, 6}; 

The sum is 78, and the product is 479001600, if you take the normal array of size 13:

int arr[13] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

It also has a sum of 78 and a product of 479001600 so your algorithm does not work.

How to find counter examples?1

To find a counter example2 3:

  1. Take an array from 0 to N - 1;
  2. Pick two even numbers3 M1 > 2 and M2 > 2 between 0 and N - 1 and halve them;
  3. Replace P1 = M1/2 - 1 by 2 * P1 and P2 = M2/2 + 1 by 2 * P2.

In the original array you have:

 Product = M1 * P1 * M2 * P2

 Sum = 0 + M1 + P1 + M2 + P2
     = M1 + M1/2 - 1 + M2 + M2/2 + 1
     = 3/2 * (M1 + M2)

In the new array you have:

Product = M1/2 * 2 * P1 + M2/2 * 2 * P2
        = M1 * P1 * M2 * P2

Sum = M1/2 + 2P1 + M2/2 + 2P2
    = M1/2 + 2(M1/2 - 1) + M2/2 + 2(M2/2 + 1)
    = 3/2 * M1 - 2 + 3/2 * M2 + 2
    = 3/2 * (M1 + M2)

So both array have the same sum and product, but one has repeated values, so your algorithm does not work.

1 This is one method of finding counter examples, there may be others (there are probably others).

2 This is not exactly the same method I used to find the first counter example - In the original method, I used only one number M and was using the fact that you can replace 0 by 1 without changing the product, but I propose a more general method here in order to avoid argument such as "But I can add a check for 0 in my algorithm.".

3 That method does not work with small array because you need to find 2 even numbers M1 > 2 and M2 > 2 such that M1/2 != M2 (and reciprocally) and M1/2 - 1 != M2/2 + 1, which (I think) is not possible for any array with a size lower than 14.

What algorithms do work?4

Algorithm 1: O(n) time and space complexity.

If you can allocate a new array of size N, then:

template <std::size_t N>
bool has_repetition (std::array<int, N> const& array) {
    std::array<bool, N> rep = {0};
    for (auto v: array) {
        if (rep[v]) {
            return true;
        }
        rep[v] = true;
    }
    return false;
}

Algorithm 2: O(nlog(n)) time complexity and O(1) space complexity, with a mutable array.

You can simply sort the array:

template <std::size_t N>
bool has_repetition (std::array<int, N> &array) {
    std::sort(std::begin(array), std::end(array));
    auto it = std::begin(array);
    auto ne = std::next(it);
    while (ne != std::end(array)) {
        if (*ne == *it) {
            return true;
        }
        ++it; ++ne;
    }
    return false;
}

Algorithm 3: O(n^2) time complexity and O(1) space complexity, with non mutable array.

template <std::size_t N>
bool has_repetition (std::array<int, N> const& array) {
    for (auto it = std::begin(array); it != std::end(array); ++it) {
        for (auto jt = std::next(it); jt != std::end(array); ++jt) {
            if (*it == *jt) {
                return true;
            }
        }
    }
    return false;
}

4 These algorithms do work, but there may exist other ones that performs better - These are only the simplest ones I could think of given some "restrictions".