Erez Shmiel - 1 year ago 65
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.

### 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".

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download