Есть ли повторяющиеся числа в массиве?

Что не так с вашим методом?

Ваш метод вычисляет некоторую статистику данных и сравнивает их с ожидаемыми для перестановки (= правильные ответы). Хотя нарушение любого из этих сравнений является окончательным (данные не могут удовлетворить ограничение), обратное не обязательно имеет место. Вы смотрите только на две статистики, и их слишком мало для достаточно больших наборов данных. Из-за того, что данные являются целочисленными, наименьшее количество данных, для которых ваш метод может потерпеть неудачу, больше 3.

Если вы ищете дубликаты в вашем массиве, есть простой способ:

int N =5;
int array[N] = {1,2,3,4,4};

for (int i = 0; i< N; i++){
for (int j =i+1; j<N; j++){
if(array[j]==array[i]){
std::cout<<"DUPLICATE FOUND\n";
return true;
}
}
}
return false;

Другой простой способ найти дубликаты — использовать контейнер std :: set, например:

std::set<int> set_int;
set_int.insert(5);
set_int.insert(5);
set_int.insert(4);
set_int.insert(4);
set_int.insert(5);
std::cout<<"\nsize "<<set_int.size();

выход будет 2, потому что есть 2 отдельных значения

Более глубокое объяснение Зачем Ваш алгоритм неверен:

1. посчитайте сумму индексов (4×5 / 2 = 10) и убедитесь, что сумма значений (3 + 4 + 1 + 2 + 0) равна этой сумме. если нет, есть повторный номер.

Учитывая любой массив A, который не имеет дубликатов, легко создать массив, который соответствует вашему первому требованию, но теперь содержит дубликаты. Просто возьмите два значения и вычтите одно из них на некоторое значение v и добавьте это значение к другому. Или возьмите несколько значений и убедитесь, что их сумма остается неизменной. (Пока новые значения все еще находятся в пределах 0 .. N-1 диапазон.) Для N = 3 уже можно поменять {0,1,2} в {1,1,1}, Для массива размера 3 есть 7 композиций, которые имеют правильную сумму, но 1 является ложным положительным результатом. Для массива размера 4 20 из 44 имеют дубликаты, для массива размера 5 — 261 из 381, для массива размера 6 — 3612 из 4332 и так далее. Можно сказать, что число ложных срабатываний растет намного быстрее чем настоящие позитивы.

2. в дополнение к первому условию, получить умножение индексов (кроме 0. так: 1x2x3x4) и проверить, равно ли оно умножению значений (кроме 0, поэтому: 3x4x1x2x0).

Второе требование заключается в умножении всех индексов выше 0. Легко понять, что это никогда не может быть очень сильным ограничением. Как только один из индексов не является простым, произведение всех индексов больше не привязывается однозначно к мультипликатам, и список может состоять из разных значений с одинаковым результатом. Например. пара 2 и 6 может быть заменена на 3 и 4, 2 и 9 могут быть заменены на 6 и 3 и так далее. Очевидно количество ложных срабатываний увеличивается поскольку размер массива становится больше, и в качестве мультипликаторов используются все больше не простых значений.

Ни одно из этих требований не является действительно сильным и не может компенсировать другое. Поскольку 0 даже не учитывается для второго ограничения, ложный положительный результат может быть создан довольно просто для массивов, начиная с размера 5. Любая пара 0 и 4 может быть просто заменена двумя 2 в любом уникальном массиве, например {2, 1, 2, 3, 2}

То, что вам нужно, это иметь результат, который уникально туго к происходящим значениям. Вы можете настроить второе требование к более сложному подходу, пропустить не простые значения и принять 0 в учетную запись. Например, вы можете использовать первое простое число в качестве множителя (2) для 0, использовать 3 в качестве множителя для 1, 5 в качестве мультипликатора для 2 и так далее. Это сработало бы (вам не понадобилось бы первое требование), но такой подход был бы слишком сложным. Более простой способ получить уникальный результат — OR i-й бит для каждого значения (0 => 1 << 0, 1 => 1 << 1, 2 => 1 << 2, и так далее. (Очевидно, быстрее проверить, был ли бит уже задан повторяющимся значением, а не ждать окончательного результата. И это концептуально то же самое, что использовать массив / вектор bool из других примеров!)