Erez Shmiel - 8 months ago 30

C++ Question

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}`

`true`

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:

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

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.

To find a counter example^{2 3}:

- Take an array from
`0`

to`N - 1`

; - Pick two even numbers
^{3}`M1 > 2`

and`M2 > 2`

between`0`

and`N - 1`

and halve them; - 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.}

**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".}