бамп

Можно сделать за один проход с выделением памяти под ещё один такой же массив. Итерируешь исходный массив, во второй массив кладешь 1 по индексу значения этого элемента. Если там уже есть 1 - значит повтор

for i 1 to n+1 do
Begin
For j 1 to n+1 do
if a=a[j] then inc(k);
if k>1 then write (a, 'повторяется');
k:=0;
End;

>>153852082
После if a(i), макаба кушает квадратные скобки

>>153851859 (OP)
Сортируешь, в цикле сравниваешь два рядом стоящих.
Или выделяешь еще один массив и ++ по индексу.

>>153852200
Я не ебу что такое линейное время.

>>153852280
Я заметил, ебанат ленивый

>>153852241
> Сортируешь
> линейное время и константу памяти

>>153851973
Массив будет не такой же, а размером с максимальное число.

>>153852280
>>153852241
Надеюсь не будущий программист.

А так, очевидный хэш-подход. Если число ограниченно, тупо делаешь второй массив, как писал первый чувак.

Посмотри как мультимножества зделоны, ихние экземпляры такими подсчетами занимаются. collections.Counter в python, например.

>>153852472
Ты долбаеб? Констанстная память? Какое нахуй хеш еблан?????

>>153851859 (OP)
Еблан тупой блядь, иди на хуй из моего IT.
Подсказка - пройтись XOR-ом.

>>153852574
Хеш не бывает константным?

>>153852574
>>153852628
Дурацкий двач. Ну так что, уёбок? Чем тебе развернуть массив на максимальное число не константно? Хэш-функция F: x->x. Это же не метод цепочек какой-нибудь.

Кретины, блядь.
https://pastebin.com/tnhNKhra

>>153851859 (OP)
>Все числа принимают значения от 1 до N
Суммируешь массив, затем вычитаешь из него сумму чисел от 1 до N (формула n*(n-1)/2), получаешь искомый ответ.

>>153852574
> Еблан тупой блядь, иди на хуй из моего IT.
> Подсказка - пройтись XOR-ом.
Сам пройдись, довен. О результатах доложишь.

>>153852718
> Повторений может быть сколько угодно.
Ещё один дебил

>>153852413
Массив чисел можно отсортировать за линейное время. Radix sort, все дела.

>>153852689
>массив на N

Нормально

>>153852729
Ну так он прав же. Ассоциативность ксора.

>>153852676-кун

>>153851859 (OP)
сортируешь масив любым из способов
сравниваешь предыдущее и следущее, если совпадают выписваешь в третий масив

>>153852776
За сколько памяти, еблан

>>153852785
Три массива

ОХУЕННО

>>153852783
повторений сколько угодно. Бляяяя, откуда вы дауны лезете?

>>153852771
Это как, блядь? У тебя по условию может повторяться только одно число (одно - 1). Или ты хочешь сказать, что одно число может повторяться несколько раз?

>>153852791
А вот это не помню.

Вообще вангую что у задачи нет решения, тут раньше был такой анон, который создавал подобные треды с нерешаемой задачкой, пока наконец кто-то не накормил его хуями с пруфами что решить ее невозможно с теми ограничениями памяти и времени что он указывал.

>>153852689
Ну и высер

1

>>153852826
Да как так блядь? Если число ограниченно, то всё есть. Как сортировка повтором.

хэш-кун

>>153852818
Окей, да.

>>153851859 (OP)
https://ideone.com/dsYRDh
уебывай чмо

>>153852886
Надеюсь тебя к кодерству не подпустят с такой писаниной

>>153852783
Где он прав, блядь? Ксор поможет только если в массиве все числа имеют пару, кроме одного искомого. Тогда ксор уберёт пары и останется результат. У опа задача совершенно противоположная.

>>153851859 (OP)
Квиксорт с тремя партишнами. = O(n)
Проходимся по массиву и проверяем єлемент с предидущим = O(n)
2O(n) = O(n)
Правда костанта памяти не війдет, так как квиксори O(n)

>>153852821
> Или ты хочешь сказать, что одно число может повторяться несколько раз?
Это. Я не оп, но других вариантов я не вижу.

>>153852886
Я в гугле работаю, хуйлоблядь.

>>153852886
Единственное правильное решение кстати.

>>153852991
>Квиксорт с тремя партишнами. = O(n)
>Квиксорт
>O(n)
Мы вам не перезвоним, уебывайте.

мимо-разработчик-в-IT-компании

>>153852778
>>153852829
По делу есть, что сказать, или кукарекание только?

>>153853040
мы вам перезвоним, если коротко

>>153853098
> кококо
Я понял.
>>153852886
Спиздил моё решение, да так, что стало нечитаемо вообще. Молодец.

>>153852689
Поясни механику решения. Я ее не совсем могу раздуплить.
Мы пробегаемся от 1 до N, берем элемент массива, стоящего по этому номеру, затем берем элемент массива, стоящего по номеру предыдущего элемента и умножаем на -1, а затем проверяем, что если элемент больше нуля - то он повторяется. Почему оно работает?

>>153853291
Здесь нету никакой логики. Это как олимпиадные задачки. Где нужно найти хакерское решение из предоставляемых данных. Ок, есть всякие разделяй-охуевай, динамическое программирование, метод ветвей и границ, бектракинг, рекурсия, гридди-алгоритмы, битовая магия, однопроходные алгоритмы. Тут нет логики. Ты сам должен её придумать, опираясь на свои знания и опыт в построении алгоритмов.

>>153853281 - кун

>>153853419
Но если оно работает - то на чем-то основано решение. На математическом факте там, да хотя бы просто детализируй алгоритм.

>>153852966
Да, я даун. Уже писал выше.

>>153853419

{1 2 3} сработает на таком алгоритме?

i = 0
a = 1
a[1] = 2
a[1] := -2

i = 1
Повторяется 2. Как так?

>>153853822
Не важно. В задании сказано, что повторения есть всегда.

>>153853291
Смотри, если бы не было ограничения на память, то задача решалась бы так. Есть массив чисел от 0 до N. Мы выделяем массив размером N и заполняем его нулями. Далее итерируем по исходному массиву и для каждого встреченного числа m мы увеличиваем счётчик во втором массиве по индексу m на единицу. Та ячейка массива, где значение больше единицы, соответствует числу, которое повторялось. Поскольку у опа есть ограничение на память, мы можем использовать исходный массив для хранения счётчика (вернее, его кастрированной формы - видели число чётное количество раз - знак плюс, нечётное - минус). Поскольку нас интересуют только значения 1 (не повторяется) и 2 (повторяется как минимум два раза), этого достаточно.

>>153853960
Вот теперь понял. Ты охуеннен.

>>153854740
Спасибо :3

>>153853960
Ебать.

>>153855127
>>153853960
А если повторяется четыре раза, то хуйня будет.

>>153853822
Это си плюс ебаное, там массивы с 1 нумеруются.

>>153855229
А мы не ждём, что оно четыре раза повторится. Повторилось два - давай досвиданье, ответ готов.

>>153851859 (OP)
А кто-нибудь уже предлагал тупо сложить все числа в массиве?

Пиздец вы тупые.

Сложить всё и вычесть N*(N+1)/2.
Всё. Время линейное, память константная.

>>153855529
Ту так это сразу "мы вам перезвоним" же.

>>153855800
И переполнение типа более чем на 90% случаев

>>153855859

У тебя "больше чем в 90% случаев" массивы больше 2^32 элементов?

Ну хорошо - тогда уточнение: выполнять все операции по модулю P, где P > N+1 и не делится на 2.

>>153855800

Сделай это на массиве
1 2 3 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 9 10
Условиям задачи он удовлетворяет.
Успехов, кек.

>>153856153
Триггер тут "Сложить всё". Меня однажды завалили на этой задачке в яндексе, когда устраивался. Сказали мол переполнение будет, досвидос.

>>153851859 (OP)
Берем переменную-аккумулятор равную нулю.
Пробегаемся по массиву и ксоким аккумулятор с индексом элемента и со значением по этому индексу.

>>153856357
В перле не будет.

>>153851859 (OP)
Просуммировал всё и вычел n(n+1)/2, получил результат.

>>153856760
Нихуя не понял.
Возьмем массив [1, 1, 1]
Просуммируем, получится 3.
Вычитаем 3(3+1)/2, получается 6.
ЧЯДНТ?

>>153857003
то есть получается -3.

>Нужно указать, какой элемент в массиве повторяется.
А вообще вы похоже неправильную задачу решаете.
Нужно указать элемент, а не значение. То есть ответом должны быть индексы.

>>153857003
>Возьмем массив [1, 1, 1]
Так ты бери который имеет смысл по условию.
n = 3,
{1,2,2}
1+2+2 = 5
3(4)/2 = 6
6-5 = 1
1+5 = 6
6/2 = 3
Ответ: третий элемент.
ОЧЕВИДНО ЖЕ

>>153857250
>третий элемент
>третий
Но тут только нулевой, первый, и второй.

Бля, я решил.

for i in array:
    array.pop(i)
    if i in array:
        print(i)

>>153857359
Время не константное.
За питонизм получаешь золотого змея. За него же получаешь кресты точены на стул.

>>153857250
В условии сказано что количество повторений может быть любым.
Из этого следует что числа не обязаны принимать каждое значение, они только МОГУТ.

>>153857359
>if i in array:
Тут неявно O(n). Общее время будет O(n^2).
Не говоря уже что нельзя менять длину листа когда обходишь его

>>153857426
Тогда это не решается.

>>153857408
Что значит константное/неконстантное время? Я не погромист.

>>153857440
>нельзя менять длину листа когда обходишь его
Кто мне запретит?

>>153857473
Идиот слепой, выше уже всё решили.

>>153857548
>>> a = [0,1,2]
>>> for i in a:
... a.pop(i)
...
0
Traceback (most recent call last):
File "<console>", line 2, in <module>
IndexError: pop index out of range

>Кто мне запретит?
Аллах.

>>153857639
>>153857541

>>153857548
>https://ideone.com/dsYRDh
Ты про эту хуйню? За такой код в продакшене тебя отпиздят после работы. Код должен быть читабельным, а не макачьими плясками. Уволен нахуй, уёбок.

>>153857639
for i in array:
if i in array.pop(i):
print(i)
а так?

>>153857768
Всё читаемо же, если ты не довн.
Мимо
>>153857807
Очевидное TypeError: argument of type 'int' is not iterable
Ты толстишь что ли?

>>153857871
Нет, не читаемо, все хуита, а ты дебил и позер. Пошел на хуй.

>>153858044
Но ведь если ты не можешь прочитать простенький код, то дебил - это ты. Зачем вообще ты сидишь в треде по алгоритмам? Пиши на пыхе что-нибудь, запихивай данные в базу. На это ты сгодишься.

>>153857871
Почему сразу толстишь, я просто эникейщик.

>>153851859 (OP)
n = rand(1,100);
a = generate_rand_array(1,n);
for i 1 to n+1 do
{
if (a > n) {
z = a - n;
} else {
z = a;
}
if (a[z] > n) { echo i . 'пиймав на вила'; }
else {a[z] = a[z] + n}
}
не прогонял. z - твоя константа, время линейное

>>153860600
n = rand(1,100);
a = generate_rand_array(1,n);
for i 1 to n+1 do
{
if (a > n) {
z = a - n;
} else {
z = a;
}
if (a[z] > n) { echo i . 'пиймав на вила'; }
else {a[z] = a[z] + n}
}
быстрофикс

>>153860698
сука йобаная вакаба не ест скобочки с i

n = rand(1,100);
a = generate_rand_array(1,n);
for p = 1 to n+1 do
{
if (a[ p ] > n) {
z = a[ p ] - n;
} else {
z = a[ p ];
}
if (a[ z ] > n) { echo i . 'пиймав на вила'; }
else {a[ z ] = a[ z ] + n}
}

>>153860763
Ну напиши ты в ideone или в wepaste хотя бы.

>>153861108
https://ideone.com/GWyt8R

>>153861713
>https://ideone.com/GWyt8R
>пиймав на вила
Проiiграв.

>>153861713
Вроде должно работать, наверно. Принцип как тут.
>>153852886

Оп-хуй, пили ещё задач. Годно.

>>153853167
Это не питона вопрос, а алгоритмов.
Python Algorithms isbn: 978-1-4302-3238-4

>>153851859 (OP)
Что значит какой элемент повторяется? Что если несколько элементов повторяются?

>>153851859 (OP)
Суммируешь все элементы массива
Вычитаешь из массива сумму от 1 до N

>>153862319
По условию повторяется только один.

>>153862387
>Вычитаешь из массива сумму от 1 до N
из суммы, конечно же

>>153851859 (OP)
Не знаю ОП тут ли ты. Решается хэш таблицей. Хэш таблица это такая штука... короч, в шарпе есть хэш таблица и при добавлении в нее элемента, она (функция Add) выдает тру если элемент в таблице уже был. Считаешь Тру перебором значений первичного массива. Радуешься жизни.

>>153864179
добавлю. хэш таблица выдает за О(1), поэтому при n элементах получается ровно линейное время.

>>153864259
> и константу памяти
И тут ты соснул с проглотом

Бля, ебать ребята вы умные. Как стать таким же?

>>153862387
Чот взлольнул. И ведь работает.

>>153865331
а нихуя. у тебя может быть дохуя повторений одного числа

>>153866817
По условию не может.

>>153866870
Ах ты ж блядь, в глаза долблюсь. Ну ладн.

Циклически проходишь по массиву, каждый непосещенный элемент a ставишь на место a[a], элемент с его места переставляешь так же. Когда очередное попадает в ячейку, где стоит такое же число, как и должно быть, ты нашёл повтор (одно число стоит на месте, другое ты переместил). Линейное время работы (одна операция с каждым элементом), две переменные (указатель на элемент массива и временная переменная).

>>153867171
Двач портит разметку. Каждый элемент массива перемещаешь в ту ячейку, индексом которой является значение этого элемента.

>>153867171
у нас есть победитель

>>153851859 (OP)
Иксором все элемнты проходишься и получаешь ответ, задача для 5б класса.

>>153867171
Лоллирую. Когда вместо программирования используют логику.

>>153867392
Лол, когда не знают, как описывают алгоритмы.

>>153867558
Ну, вот если бы оно работало для произвольных чисел а не для [1..n], вот тогда это хотя бы как-то можно было назвать. Охуеть, блядь, алгоритм.

>>153867708
ты довн, оно и должно работать для [1..N]

>>153867708
ТИМЛИД ВРЫВАЕТСЯ В ПОМЕЩЕНИЕ
@
СЫЧЁВ БЛЯДЬ СРОЧНО У НАС ПРОЕКТ НЕ ЗАКРЫТ ПИШИ ЕБАНЫЙ МОДУЛЬ
@
КИДАЕТ ТЗ НА СТОЛ, ЗАТЯГИВАЕТСЯ ВЕЙПОМ, ХЛОПАЕТ ДВЕРЬЮ
@
ВЕЧЕРОМ ВВАЛИВАЕТСЯ В ОФИС, ПРОСИТ ПОКАЗАТЬ, ЧТО СДЕЛАЛ ЗА ДЕНЬ
@
А НУ НОРМ НО ЧОТ МОГЛО БЫТЬ ЛУЧШЕ, ТЫ НЕ МОГ СДЕЛАТЬ ЧТОБ ПОД ЛЮБЫЕ ВХОДНЫЕ РАБОТАЛО А НЕ ТОЛЬКО КАК В ТЗ?
@
ПРЕМИЮ ТВОЮ ВЫПИШУ НА СЕБЯ

>>153867171
лел. конечно собъется когда вдруг на месте i сгенерится число i.
>>153851859 (OP)
создаешь зануленный массив длинной N+1
проходишь по оригинальному массиву, i во втором массиве сравниваешь с нулем. если да - меняешь на единичку, если нет - каунтер повышаешь на единичку.

>>153862292
Но алгоритм потом вбиваете же в какой-нибудь язык программирования

>>153870241
а вероятность первого пункта - 1- (n!)/(n)^n
что по формуле Стирлинга стремится к 1 для больших n. Учи матан>>153867171

>>153870241
пардон ый элемент

>>153870764
iтый блять

>>153870718
и тервер.

>>153851859 (OP)
myarray = ()
foreach(array as elem){
if( not_in_array( myarray, elem ) ) {
myarray[elem]++
}
}
unset(myarray, elem = 1)

foreach(myarray as key val){
print key 'повторяется' val 'раз'
}

>>153870777
>>153870950
>>153870764
>>153870718
Я не прав. Тот парень со сменой элементов прав. Сорян. Красавчик че.

>>153870777
>>153870950
>>153870764
>>153870718
Я не прав. Тот парень со сменой элементов прав. Сорян. Красавчик че.

Складываешь все числа, считаешь сумму от 1 до n по формуле, вычитаешь из первого второе

>>153851859 (OP)
>N+1
>от 1 до N
Ебать ты тупой. То есть, допустим у нас есть масив длиной 6 (N=5) с числами 1 2 3 4 5? Где ещё одно число, сучка?

>>153872602
Хуя ты довен.

>>153872414
Единственно что нужно добавить. Что после сравнения и перемещения нужно снова проверить перемещенный с того места элемент и если его i не совпадает - переместить(т.е. запустить рекурсию по элементу до тех пор пока либо не переберется весь массив (тогда значение в ячейкие совпадет с порядковым номером) либо пока не найдём равное значение. Тогда из рекурсии выходим и идём к следующему элементу

>>153851973
[eq

>>153872602
>1 2 3 4 5
Может быть и
1 2 3 4 5 5
и
1 2 3 4 4 4

Суммируешь все элементы и вычитаешь сумму от 1 до N
thread ne chital

>>153873590
Бля, я даун, они ж повторяться могут

>>153873370
Бля я думал это по порядку типа [1; N] (что даже читается "от единицы до N").

>>153873003 >>153873370
Блять нельзя написать "каждое число". Взяли написали "все числа".

>>153851859 (OP)
Если в массиве повторяется только одно число, а все остальные от 1 до Н, то элементарно - считаем за константу арифметическую последовательность от 1 до Н, затем за линейное время считаем сумму всех элементов и за константу вычитаем одно из другого. Это ответ.

>>153875550
еще один тред не читал. довен

>>153851859 (OP)
>N+1
>от 1 до N
>Повторений может быть сколько угодно
Нет, в таком случае повторение может быть только одно.

>>153873370
>1 2 3 4 4 4
Не может, потому чтов этом нет 5

>>153875809
может не быть пятерки. единственное ограничение на массив - элементы не превосходят N

сверяешь первый со вторым и до конца массива - учитываешь результат (строишь алгоритм так чтоб при совпадении не попало в повторное сравнение).
сверяешь второй с третьим и до конца массива (строишь алгоритм так чтоб при совпадении не попало в повторное сравнение).
и так далее.

>>153876773
У любого алгоритма (обычно имеется ввиду однообразно повторяющиеся, циклические штуки) есть сложность. Например, если обработка 10 элементов (цифр, например) требует 100 циклов вычислений, то алгоритм имеет степень сложности nn - квадратичный. "Линейная" сложность - это когда на n элементов нужно n+a или, в худшем случае, na при a<n циклов.

Константа памяти - конкретно здесь значит хуйню, но в общем случае имеется ввиду, что памяти для решения выделяется конечное количество, причём логически "подходящее" под условие задачи, чтобы для итерации 10 целочисленных значений твоей проге не требовалось 10 Гб памяти.

>>153877366
Блядская разметка.

>>153877366
>конкретно здесь значит хуйню
Конкретно здесь это означает, что нельзя создать контейнер размера N, в котором отмечать, встречалось такое число или нет.

>>153877366
>"Линейная" сложность - это когда на n элементов нужно n+a или, в худшем случае, na при a<n циклов.
А вот тут какая? >>153877207

>>153879413
Ещё немного, и будет "пузырёк".

>>153853960
очень хорошо, а что мы делаем когда все биты заняты чем-то полезным.

>>153851859 (OP)
Достаточно попробовать выстроить массив по порядку. Если a != i, то меняем местами элементы a и a[a], если они равны, то печатаем результат и выходим

https://pastebin.com/wsTQ2sak

https://pastebin.com/bZEwWVAi

>>153889110
Ой, извините, совсем хуйню написал, не читайте, пожалуйста.

>>153852991
Хохлогромист