Задачка на подумать

@spvert · Регистрация: 25.11.2017

Author24 — интернет-сервис помощи студентам

Задачка для начинающих С-шников на подумать.
Дано: массив целочисленных неотрицательных значений размером, ну скажем, 1000000001 (один миллиард один) элемент, заполненный одним одним миллиардом парных (парное число встречается в массиве 2 раза) и одним непарным числом.
Задача: найти это единственное непарное число.

Байт · 11.01.2018, 21:39

spvert, а какие ограничения? 1.O(N), 2.O(NlnN), 3.O(N²)?
Случай 3 - тривиален.
Случай 2 - я догадываюсь
Случай 1 - Увы! Ничего путнего в голову пока не приходит.
И можно ли использовать дополнительные массивы, хотя бы размером MAX_INT/8 ?

@spvert · 11.01.2018, 21:45 **[ТС]**

Случай 3 тривиален, но размер имеет значение. 10⁹ элементов. O(N2) дает 10¹⁸ операций. Если предположить, что 1 операция это 1 процессорный такт (что в общем, для данного случая, сильно некорректно, т.к. операции с памятью занимают больше 1 такта), то для 3 ГГц результат будет ожидаться... сколько поколений? -)

Случай 2 - предлагайте.

Случай 1 - решение действительно есть.

Дополнительные массивы создавайте на здоровье.

Байт · 11.01.2018, 22:02

Сообщение от spvert

результат будет ожидаться... сколько поколений?

Согласен на все 100. Спросил для полноты

Сообщение от spvert

Случай 2 - предлагайте.

Помолчу пока. Не такой уж я начинающий

Пусть ребята репу почешут.

Сообщение от spvert

Случай 1 - решение действительно есть.

Если без дополнительных массивов, то очень интересно. А с дополнительными - 2 пальца. Заводим массив, используя его как битовую шкалу. Встретилось число - соответствующий бит +1 (mod 2). Останется единственный бит, равный единице.

@spvert · 11.01.2018, 22:22 **[ТС]**

Ответ, предполагаю, опубликовать завтра. Часиков в 10 вечера по Москве. -)
Ну а конкретно Байт, могу кинуть в личку.

@Olej · 11.01.2018, 22:31

Сообщение от spvert

Ну а конкретно Байт, могу кинуть в личку.

Так Байт уже написал полностью удовлетворительное решение O(N) уже 20 минут назад ... и без всякой лички.

@spvert · 11.01.2018, 22:33 **[ТС]**

Есть решение без дополнительных массивов. -)
И в решении Байта есть один нюанс - дополнительный массив тоже надо чистить.
И, кстати, битовая шкала это круто - т.е. массив заводится размером 2³² / 8?
В случае 64-х бит это будет смотреться фейерично -)

Байт · 11.01.2018, 22:37

Сообщение от Olej

Так Байт уже написал полностью удовлетворительное решение O(N) уже 20 минут назад

Не, я там массив здоровенный использую. Что мне разрешили, но в самом деле это не делает мне чести.

Сообщение от spvert

Ответ, предполагаю, опубликовать завтра. Часиков в 10 вечера по Москве. -)
Ну а конкретно Байт, могу кинуть в личку.

Не надо. Торопиться мне некуда. Даже наоборот, будет над чем подумать до 10-ти вечера.

Не по теме:

А так-то... Всегда приятно пообщаться с хорошим человеком.:)

@spvert · 11.01.2018, 22:44 **[ТС]**

Olej, представьте себе решение этой задачи если у вас 1 МБайт оперативной памяти.
Уж больно Никлаус Вирт любил такие задачи.
Да и во времена не столь отдаленные массивы данных часто перевешивали 48 КБайт оперативки.
И сейчас BigData создает объемы данных для переработки больше оперативки

~~Остап Бонд~~ · 11.01.2018, 23:35

Решение?

@spvert · 11.01.2018, 23:44 **[ТС]**

Тадааам!
И у нас есть победитель.
Действительно, решение - XOR всех элементов массива.
Результат - единственное непарное число.
Честный O(N) без дополнительных массивов.

P.S. Честно - сами додумались или подсказал кто?

~~Остап Бонд~~ · 12.01.2018, 00:00

Не по теме:

Вторая ссылка в гугле - найти уникальное число среди парных.
По первой чушь какая-то на хабрахабре%-)

Байт · 12.01.2018, 00:08

Остап Бонд,

Но, простите, с чем же мне сегодня засыпать?

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

HighPredator · 12.01.2018, 10:21

Побитовые операции: в массиве определить число, которое не имеет пары, с использованием xor

Добавлено через 50 секунд
Под си допиливается на раз.

@spvert · 12.01.2018, 13:26 **[ТС]**

HighPredator, данная тема не запрос на программу.
Это была попытка разнообразить поток однотипных непонимаек или нежелаек, чтобы многоуважаемые Доны могли развлечься. К сожалению, данная задачка уже успела засветиться в интернете, а потому ее считили.
Придумаю другую. -)

HighPredator · 12.01.2018, 13:39

Не по теме:

spvert, я к тому что она древняя как я не знаю что и тут была в т.ч.

Байт · 12.01.2018, 14:49

Не по теме:

HighPredator, Однако, трудно найти под этой луной что-то действительно новенькое. А лично для меня ново то, что я вижу в первый раз (или успел забыть). И усилия уважаемого spvert достойны всяческих похвал. :)

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
	12.01.2018, 13:26 [ТС]	15
	HighPredator, данная тема не запрос на программу. Это была попытка разнообразить поток однотипных непонимаек или нежелаек, чтобы многоуважаемые Доны могли развлечься. К сожалению, данная задачка уже успела засветиться в интернете, а потому ее считили. Придумаю другую. -) 1

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
		1
	Задачка на подумать 11.01.2018, 21:24. Показов 1155. Ответов 16 Метки нет (Все метки) Задачка для начинающих С-шников на подумать. Дано: массив целочисленных неотрицательных значений размером, ну скажем, 1000000001 (один миллиард один) элемент, заполненный одним одним миллиардом парных (парное число встречается в массиве 2 раза) и одним непарным числом. Задача: найти это единственное непарное число. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	11.01.2018, 21:39	2
	spvert, а какие ограничения? 1.O(N), 2.O(NlnN), 3.O(N²)? Случай 3 - тривиален. Случай 2 - я догадываюсь Случай 1 - Увы! Ничего путнего в голову пока не приходит. И можно ли использовать дополнительные массивы, хотя бы размером MAX_INT/8 ? 0

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
	11.01.2018, 21:45 [ТС]	3
	Случай 3 тривиален, но размер имеет значение. 10⁹ элементов. O(N2) дает 10¹⁸ операций. Если предположить, что 1 операция это 1 процессорный такт (что в общем, для данного случая, сильно некорректно, т.к. операции с памятью занимают больше 1 такта), то для 3 ГГц результат будет ожидаться... сколько поколений? -) Случай 2 - предлагайте. Случай 1 - решение действительно есть. Дополнительные массивы создавайте на здоровье. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	11.01.2018, 22:02	4
	Сообщение от spvert результат будет ожидаться... сколько поколений? Согласен на все 100. Спросил для полноты Сообщение от spvert Случай 2 - предлагайте. Помолчу пока. Не такой уж я начинающий Пусть ребята репу почешут. Сообщение от spvert Случай 1 - решение действительно есть. Если без дополнительных массивов, то очень интересно. А с дополнительными - 2 пальца. Заводим массив, используя его как битовую шкалу. Встретилось число - соответствующий бит +1 (mod 2). Останется единственный бит, равный единице. 0

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
	11.01.2018, 22:22 [ТС]	5
	Ответ, предполагаю, опубликовать завтра. Часиков в 10 вечера по Москве. -) Ну а конкретно Байт, могу кинуть в личку. 0

@Olej 322 / 170 / 24 Регистрация: 25.03.2012 Сообщений: 712
	11.01.2018, 22:31	6
	Сообщение от spvert Ну а конкретно Байт, могу кинуть в личку. Так Байт уже написал полностью удовлетворительное решение O(N) уже 20 минут назад ... и без всякой лички. 0

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
	11.01.2018, 22:33 [ТС]	7
	Есть решение без дополнительных массивов. -) И в решении Байта есть один нюанс - дополнительный массив тоже надо чистить. И, кстати, битовая шкала это круто - т.е. массив заводится размером 2³² / 8? В случае 64-х бит это будет смотреться фейерично -) 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	11.01.2018, 22:37	8
	Сообщение от Olej Так Байт уже написал полностью удовлетворительное решение O(N) уже 20 минут назад Не, я там массив здоровенный использую. Что мне разрешили, но в самом деле это не делает мне чести. Сообщение от spvert Ответ, предполагаю, опубликовать завтра. Часиков в 10 вечера по Москве. -) Ну а конкретно Байт, могу кинуть в личку. Не надо. Торопиться мне некуда. Даже наоборот, будет над чем подумать до 10-ти вечера. Не по теме: А так-то... Всегда приятно пообщаться с хорошим человеком.:) 0

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
	11.01.2018, 22:44 [ТС]	9
	Olej, представьте себе решение этой задачи если у вас 1 МБайт оперативной памяти. Уж больно Никлаус Вирт любил такие задачи. Да и во времена не столь отдаленные массивы данных часто перевешивали 48 КБайт оперативки. И сейчас BigData создает объемы данных для переработки больше оперативки 0

~~Остап Бонд~~ Заблокирован
	11.01.2018, 23:35	10
	Сообщение было отмечено spvert как решение Решение Решение? 2

@spvert 229 / 112 / 35 Регистрация: 25.11.2017 Сообщений: 389
	11.01.2018, 23:44 [ТС]	11
	Тадааам! И у нас есть победитель. Действительно, решение - XOR всех элементов массива. Результат - единственное непарное число. Честный O(N) без дополнительных массивов. P.S. Честно - сами додумались или подсказал кто? 0

~~Остап Бонд~~
	12.01.2018, 00:00 #12
	Не по теме: Вторая ссылка в гугле - найти уникальное число среди парных. По первой чушь какая-то на хабрахабре%-) 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	12.01.2018, 00:08	13
	Остап Бонд, Но, простите, с чем же мне сегодня засыпать? А я, знаете, люблю по примеру отца русской Водки, товарища Менделеева, засыпать под хорошую задачку... 0

HighPredator 6045 / 2160 / 753 Регистрация: 10.12.2010 Сообщений: 6,005 Записей в блоге: 3
	12.01.2018, 10:21	14
	Побитовые операции: в массиве определить число, которое не имеет пары, с использованием xor Добавлено через 50 секунд Под си допиливается на раз. 0

HighPredator
	12.01.2018, 13:39 #16
	Не по теме: spvert, я к тому что она древняя как я не знаю что и тут была в т.ч. 0

Байт
	12.01.2018, 14:49 Задачка на подумать #17
	Не по теме: HighPredator, Однако, трудно найти под этой луной что-то действительно новенькое. А лично для меня ново то, что я вижу в первый раз (или успел забыть). И усилия уважаемого spvert достойны всяческих похвал. :) 0