Задачки для новичков

[Adelf]

А ну да.. не заметил
Но в любом случае O(N * log N) сложность у него.

 

[Sender]

array_count_values, дальше дело техники

 

[Sender]

еще как вариант sort, потом идти по массиву пока не найдем одинокое число

но конечно с xor вариант самый интересный

 

[workOnFood]

zerkms

$r = 0;
foreach ($a as $v) {
    $r ^= $v;
}
var_dump($r);

Потестил ваш код. Почитал про побитовые операторы. Хоть убей не пойму в чём его суть. var_dump($r) возвращает 5085 что не соответствует не одному из элементов массива.
И что значит ^= комбинация исключающего или и оператора присвоить.
Проводил такие эксперименты.

$r=0;
$r ^= 0;\\ $r == 0
$r ^= 1;\\ $r == 1
$r ^= 2;\\ $r == 2
$r ^= 3;\\ $r == 3
....

В чём дело? Помогите разобраться или дайте ссылку с теоретическим материалом.

 

[fixxxer]

zerkms

Потестил ваш код. Почитал про побитовые операторы. Хоть убей не пойму в чём его суть. var_dump($r) возвращает 5085 что не соответствует не одному из элементов массива.

> php -r '$arr=array(1,1,2,2,3,3,4,4,5,5,6,6,7,7,8);$r=0;foreach($arr as $v)$r^=$v;var_dump($r);'
int(8)
ты уверен что выполняешь условие задачи в плане того что должно быть в массиве?

И что значит ^= комбинация исключающего или и оператора присвоить.

то же самое как += итд

В чём дело? Помогите разобраться или дайте ссылку с теоретическим материалом.

http://ru.wikipedia.org/wiki/Сложение_по_модулю_2

 

[workOnFood]

fixxxer

ты уверен что выполняешь условие задачи в плане того что должно быть в массиве?

Сделал такой же тест с маленьким массивом всё работает норм. Я формировал массив вот так

$arr=array();
$n=0;
$sw=1;
for($i=0;$i<=10001;$i++){
	$arr[]=$n;
	if($n==84)$n++;
	else{
		if($sw==2){
			$n++;
			$sw=0;
		}
		$sw++;
	}
}

При этом вот эти два варианта выдают правильное значение.

// Первый вариант
$arr=array_count_values($arr);
$num=array_search(1,$arr);
echo $num;

//Второй вариант
sort($arr);
for($i=0;$i<count($arr);$i+=2){
	if($arr[$i]!=$arr[$i+1]){echo 'Нашёл!!! это число = '.$arr[$i];break;}
}

то же самое как += итд

Это надо переварить))

 

[Sender]

workOnFood
видимо что-то во входных данных

        $max = 10001;
        $one = rand(1, $max);
        $array = array();
        
        for($i=1; $i<=$max; $i++) {
                $array[] = $i;
                
                if ($i != $one)
                        $array[] = $i;
        }
        
        shuffle($array);
        
        $r = 0;
        
        foreach($array as $v)
                $r ^= $v;
        
        echo $one.' '.$r;

выдает все правильно

 

[Adelf]

$r=0;
$r ^= 0;\\ $r == 0
$r ^= 1;\\ $r == 1
$r ^= 2;\\ $r == 2
$r ^= 3;\\ $r == 3

чушь

 

[workOnFood]

Adelf
Я имел ввиду что каждая из этих строк по отдельности даёт такое значение, или ты из-за комментариев?

 

[Adelf]

workOnFood
комментарии странные. не те слеши.
а значения неверные.
0, 1, 3, 0 должно было быть.

 

[workOnFood]

Sender
Ну да всё правильно выдаёт. Только непонятно почему. Если создать небольшой массив и просмотреть визуально с помощью моего кода всё правильно да и если без XOR делать всё норм.

 

[workOnFood]

Adelf

комментарии странные. не те слеши.
а значения неверные.
0, 1, 3, 0 должно было быть.

Ну да это выдаст если весь код сразу запустить просто выразился неверно. А комменты так поставил потому что код писал сразу в форму.) Не разу так делать не пробовал думал так можно.

 

[Sender]

workOnFood
у тебя неправильно формируются исходные данные, при определнных параметрах ты нарушаешь условие задачи инфа 100%

 

[fixxxer]

все там правильно будет, где то ты неправильно генерируешь входной массив.

и да - если знаешь что такое raid 5 подумай как они устроены

 

[Adelf]

workOnFood
у XOR есть одно отличительное свойство. если на какое-либо число применить XOR любым другим числом два раза, то результатом будет исходное число.
Ну и второе свойство еще - насчет нуля. Все видно в формулах:
x ^ 0 = x
(x ^ y) ^ y = x.
как результат - решение данной задачи. Все "двойные" числа "исчезнут" изза второй формулы, а единственное число - останется, изза комбинации этих формул..
правда там еще свойство аддитивности нужно(которое у этой операции тоже есть - фактически более общий вариант правила "от перемены мест слагаемых сумма не меняется"), т.е. все немного сложнее, но смысл верный

 

[workOnFood]

Sender

у тебя неправильно формируются исходные данные, при определнных параметрах ты нарушаешь условие задачи инфа 100%

Да точно с нечётными числами получается два неповторяющихся числа, и поэтому работают те два варианта)

 

[workOnFood]

zerkms
Разобрался с кодом. Снос башки))) Получается что в переменную пишутся двоичные данные и когда встречается аналогичная переменная все 1 меняются на 0 и в конце остаются только те которые соответствуют искомому числу. Очень клёвая задачка. Многому научился.

ЗЫ Хочу ещё)

 

[workOnFood]

Adelf
Ага спасибо что разжевал, хотя я допёр раньше чем прочитал пост)) Но очень наглядно.

 

[Sender]

кстати, вариант с array_count_values не шибко то и отстает, помедленнее конечно, но на 1000001 числах разница секунда при времени выполнения 4-5 сек

памяти конечно жрет больше

 

[Sender]

workOnFood
http://www.facebook.com/careers/puzzles.php

попробуй вот это, мне нравится, интересные задачки