26.03.2016 06:58
sim0nsays 110 17300 Источник
А вот задачка на выходные! Она плохо подходит, чтобы спрашивать на собеседовании, потому что слишком уж на инсайт (пожалуйста, никогда не задавайте такие на собеседованиях), и слишком простая для соревнований. Как раз чтобы доставить тот самый satisfying click в мозгу, за который мы любим программирование. Итак:

Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).

Не забывайте использовать тег <spoiler> для решений в комментариях!

тривиальное решение: заводим нулевой битовый массив на 4Г битов (константная память!). если мы видим какое-то число то делаем на его позиции исключающее или с единицей. в конце только два бита будут равны одному — это и есть те числа что мы искали. в один проход по дополнительному массиву можно их найти.
Не троллить :) Давайте, чтобы не было разночтений — памяти у вас четыре килобайта.

Одно из решений
Как легко заметить, парные числа намекают, что задача про xor!
Пусть искомые числа — X и Y. Если просто сделать xor всех чисел в массиве, понятно что результатом будет X^Y, что хорошо тем, что все другие числа сократились, но плохо тем, что возможности их вычислить не дает. Что делать?
Заметим, что если бы мы заранее знали в каком бите числа X и Y отличаются (а такой бит быть обязан), то задача бы решалась просто — давайте сделаем xor всех чисел, у которых в бите N скажем единица. Все парные числа сократятся, и результатом будет X или Y. А если у нас есть еще и значение X^Y, то и второе число просто вычислить.
Более того, если у нас есть X^Y это еще и говорит, в каком бите X и Y отличаются — там где в xor 1.
Осталось понять как это сделать за один проход.
Давайте во время прохода насчитывать xor всех чисел и 32 аккумулятора. В i-ом аккумуляторе мы будем накапливать xor всех чисел, у которых 1 в i-м бите. В конце воспользуемся одним из аккумуляторов, где биты различаются.

В комментариях тоже много решений, с кодом и без, вот некоторые (список не претендует на полноту):
Решение от kmu1990
Решение от Ogra
Решение от ZyXI
Как решали бы задачу в стартапе от Demogor
Развитие задачи от deniskreshikhin
Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.

Комментарии (110)


  1. rPman
    26.03.2016 20:55
    #8823026
    -4

    Самое тупое и простое решение, не эффективное O(n^2)
    текущий минмум = 0 (точнее минимально возможное число, способное быть записано в 32бита, т.е. для чисел со знаком это -2,147,483,648)
    цикл в (размер массива/2) итераций
    {
    текущее количество = 0
    для каждого элемента массива
    {
    ищем количество чисел равных текущему минимуму (если элемент равен текущему минимуму то увеличиваем количество)
    ищем следующий минимум (число больше текущего минимума и меньше или равно текущему элементу)
    }
    если количество чисел было больше 1 то выводим текущий минимум
    }


    1. rPman
      26.03.2016 21:07
      #8823046

      Черт, ошибку нашел у себя:

      размер внешнего цикла нужно исправить на деление с округлением в большую сторону +1 или просто тупо +2, иначе для случая когда искомые числа максимальные для массива — они не будут найдены)
      либо цикл бесконечный и выходим, когда не сможем найти следующий минимум (но тогда будет доп условие)


  1. mgrigorov_ua
    26.03.2016 21:34
    #8823088
    +2

    Такие задачи у меня всегда вызывают чувство ущербности…
    И вроде программистом себя считаешь и вроде на работу ходишь каждый день, а всё равно, никуда не заглядывая, решить не можешь.
    Да чего там… подглядывая в спойлеры, мало чего понял :(
    Жду решения с детальным разжевыванием!
    Спасибо.


    1. sim0nsays
      26.03.2016 21:35
      #8823092

      Ну, в реальной работе (к сожалению) такое нужно крайне немногим и крайне редко. Для меня это скорее радостная возможность вспомнить молодость и размять мозги.


      1. deniskreshikhin
        26.03.2016 23:11
        #8823228

        Ну, в реальной работе (к сожалению) такое нужно крайне немногим и крайне редко.

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


        1. gecube
          27.03.2016 02:29
          #8823518
          +2

          А ее и ненужно разбирать. Код на XOR реально эффективный будет, а map — медленный отстой (в этом случае). Читаемость заменяется комментариями, а код обрамляется в функцию (типа черный ящик).


          1. deniskreshikhin
            27.03.2016 02:39
            #8823530

            Ага, покрасить и выбросить -)


        1. sim0nsays
          27.03.2016 04:47
          #8823592
          +1

          Ну, шанс что выпадет именно такая задача вообще бесконечно мал, слишком уж искусственно. А вот шанс использовать битовую магию, про которую задача — почему нет.
          Прием с xor указателей в списке вполне рабочий, к примеру.
          Разумеется, если память и/или производительность неважна — лучше писать проще.


  1. Demogor
    27.03.2016 02:53
    #8823548
    +3

    Легкий сарказм
    Вариабельное решение на js:
    var r={};
var a=[1,1,2,5,7,7,11,12,11,12];
a.forEach((x)=>{
  if(!r[x])
    r[x]=1;
  else
    delete r[x];
});

    Если повезет — то дубляжи будут попадаться достаточно часто и размер объекта r будет скакать в пределах 4к. Превысило? Ну что ж, не повезло.


    1. sim0nsays
      27.03.2016 04:49
      #8823594
      +4

      ыыыыыыыы! И надеемся, что у первых кастомеров объемы маленькие, а там глядишь до следующего раунда инвестиций дотянем!


      1. Demogor
        27.03.2016 10:52
        #8823774
        +2

        Нормальная русская рулетка: отвалится/не отвалится в момент сдачи.


  1. govnokoder
    27.03.2016 05:05
    #8823596

    Искомые числа: X1 и X2
    Кол-во элементов: CA
    Считаем сумму всех чисел (SA), XOR всех чисел (XA)
    Получаем: SA = 2a + 2b + 2c +… + X1 +… + X2 +…
    XA = X1 ^ X2
    Перебираем первое число от 0 до 0xfffffff так, чтобы выполнялось равенство: (SA + X1 + (X1 ^ XA)) / CA — целое


    1. sim0nsays
      27.03.2016 05:06
      #8823598

      ааааа, термояд! Пишите под спойлером плз.

      Кажется, контрпример
      Два двухбитовых числа:
      1 1 и 1 0


    1. Demogor
      30.03.2016 07:36
      #8829016

      Если я не ошибаюсь, это будет не 1 проход, а 3(сумма, xor, перебор)?


  1. ZyXI
    27.03.2016 05:23
    #8823600
    +1

    Решение
    Решение простое: заводим 65 «аккумуляторов»: в нулевой xor’ятся абсолютно все числа массива по мере прохода по нему. Т.к. a^a=0, a^b=b^a, a^0=a, a^(b^c)=(a^b)^c, то в аккумуляторе в результате оказывается а0=u1^u2, где u1 и u2 — искомые уникальные числа. Получив u1^u2 нужно как?то это разделить на u1 и u2, для этого используем то, что u1?u2 (свойство уникальности). Т.к. u1?u2, то хотя бы один бит в u1 отличен от u2, поэтому оставшиеся 64 аккумулятора используются так: в n’й аккумулятор (n=1..64) xor’ятся числа, (n//2)?й бит которых равен (n%2) (// — целочисленное деление). Таким образом образуются 32 группы по два аккумулятора: в первой группе 1?й и 2?й, во второй 3?й и 4?й, … Из?за того, что существует хотя бы один бит, отличный от u1 и u2, существует такая группа аккумуляторов, что u1 учавствовал в определении значения одного аккумулятора, в определении значения которого не учавствовал u2. В такой группе один из аккумуляторов равен u1, а другой u2. В группах, где u1 и u2 имеют совпадающий бит один из аккумуляторов 0, а другой — u1^u2. Если u1 или u2 равен 0, то все группы будут иметь одинаковые пары значений.
    Код на Python:
    #!/usr/bin/python3.4

import random

from functools import partial

from numpy.random import random_integers, shuffle
from numpy import array, uint32, unique, array_equal

def create_test_array(randsize=10000):
    random_uints32 = partial(random_integers, 0, 2 ** 32 - 1)

    doubles = unique(random_uints32(size=randsize))

    u1 = next(iter(doubles))
    while u1 in doubles:
        u1 = random_uints32()

    u2 = next(iter(doubles))
    while u2 in doubles:
        u2 = random_uints32()

    arr = array(doubles, dtype=uint32)
    arr.resize([len(doubles) * 2 + 2])
    arr[len(doubles):len(doubles) * 2] = doubles
    arr[-2] = u1
    arr[-1] = u2
    shuffle(arr)
    return u1, u2, arr

def find_uniques(arr):
    acc0 = uint32(0)
    accs = array([[acc0] * 2] * 32)
    masks = array([uint32(1 << i) for i in range(32)])

    for val in arr:
        acc0 = acc0 ^ val
        for bitidx, subaccs in enumerate(accs):
            subaccs[int(bool(val & masks[bitidx]))] ^= val

    p1 = array([acc0, uint32(0)])
    p2 = array([uint32(0), acc0])

    for subaccs in accs:
        if array_equal(subaccs, p1) or array_equal(subaccs, p2):
            continue
        return subaccs

    return p1

def main():
    u1, u2, arr = create_test_array()
    fu1, fu2 = find_uniques(arr)
    print('expected: ', sorted([u1, u2]))
    print('found   : ', sorted([fu1, fu2]))

if __name__ == '__main__':
    main()

    PS: комментарии пока не читал.


    1. sim0nsays
      27.03.2016 05:25
      #8823602

      Все так!


      1. ZyXI
        27.03.2016 05:37
        #8823604

        Уточнение
        Я тут после прочтения комментариев понял, что вообще?то acc0 не нужен: в группах всегда будет либо (0, u1^u2), либо (u1, u2). Т.е. можно забить на acc0 и возвращать первую пару, где оба аккумулятора не нули. А если таких нет, то вернуть самую первую пару: это вариант, когда u1 или u2 0. Эта переменная вообще появилась из?за того, что первым соображением было «если всё xor’ить, получим u1^u2; теперь думаем, как получить отсюда u1 и u2». В комментариях некоторые люди здесь и застряли.
        def find_uniques(arr):
    accs = array([[uint32(0)] * 2] * 32)
    masks = array([uint32(1 << i) for i in range(32)])

    for val in arr:
        for mask, subaccs in zip(masks, accs):
            subaccs[int(bool(val & mask))] ^= val

    for subaccs in accs:
        if subaccs[0] != 0 and subaccs[1] != 0:
            return subaccs

    return accs[0]


  1. vasiatka
    27.03.2016 08:59
    #8823654

    оставю тут. сложность O(n). память O(1). guildalfa.ru/alsha/node/29


  1. savinov_ao
    27.03.2016 19:17
    #8824486
    +1

    Напишу всё же свое предположение, хотя оно не укладывается в более жесткие требования предложенные Zealint.
    Берем первые 10 простых чисел P={2, 3, 5, 7, 11, 13, 17, 19, 23, 29}. Их сумма 129. Выделяем bool d[129]; Реализуем функцию Mods(x), которая возвращает массив из 10 чисел: i-e число равно (x % P[i]) + сумма P[0..i-1].
    Для всех элементов i=1..N
    1. M=Mods(a[i]). Инвертируем d[M[j]] для j=0..9
    2. Считаем xy ^= a[i]

    Затем для x=0..232-1 вычисляем y = xy ^ x и проверяем что xor массивов Mods(x) и Mods(y) совпадает с d. Если совпадает, выходим по break.
    Наверное так.


  1. ankh1989
    28.03.2016 10:24
    #8825164

    Можно например сначала сложить все числа в конечном поле, затем сложить квадраты этих чисел. В итоге пары сократятся и получится два уравнения: сумма двух числе и сумма их квадратов. Уравнения эти сводятся к выичслению квадратного корня в конечном поле, что можно сделать алгоритмом Шенкса. Проще конечно xor-ом, но если хочется загрузить того кто собеседование проводит, то конечные поля Галуа — самое то.


    1. sim0nsays
      28.03.2016 10:27
      #8825168

      ооооо! В конченом поле — это как? По модулю? И почему пары сократятся?


    1. halyavin
      29.03.2016 09:20
      #8827130
      +2

      Квадраты бесполезны, поскольку x2+y2=(x+y)2 — мы не получаем новой информации. Нужно

      Решение
      использовать кубы. x3+y3=(x+y)(x2+xy+y2). Таким образом мы узнаем x2+xy+y2. Как мы видели выше, сумму квадратов мы уже знаем. Вычитая ее, получаем xy. Остается решить квадратное уравнение и найти x и y. Это единственное (из предложенных в комментариях) правильное решение задачи, поскольку 32 аккумулятора — это не O(1), а O(w), где w — размер машинного слова.


      1. sim0nsays
        29.03.2016 09:36
        #8827158

        Так поясните, что подразумевается под сложениями и умножениями, и как сокращаются пары других чисел?


        1. halyavin
          29.03.2016 21:08
          #8828494
          +1

          Сложение — xor. Умножение выполняется сложнее. Вначале нужно выполнить битовое умножение без переносов, а потом посчитать CRC. Еще материал по этой теме: https://habrahabr.ru/post/212095/


        1. ankh1989
          30.03.2016 09:07
          #8829076

          Практически это делается так:
          shl = x => x = x << 1 ^ (x < 0? 0x8d: 0); // x * 2 + 2**32 + 0x8d
          mul = (a, b) => b && ((b & 1? a: 0) ^ shl(mul(a, b >>> 1)));
          А потом применяем вот так:
          mul(0x6789, 0x9876);


      1. Zealint
        29.03.2016 10:30
        #8827238

        Скрытый текст
        Размер исходных чисел строго ограничен константой — 32 бита. Далее, размер входного потока по условиям задачи тоже строго ограничен (максимум, у нас два раза каждое число встречается), поэтому, строго говоря, тут любое решение будет константным как по времени, так и по памяти. Если же отбросить троллинг и сделать вид, что задача поставлена правильно, то завести 32 аккумулятора будет вполне законным решением. Ваше решение разве не зависит от размера слова? Так ли это?


        1. Mrrl
          29.03.2016 11:09
          #8827308

          Ваше решение разве не зависит от размера слова?

          Зависит — примерно как 3*N бит. А решение со счётчиками — примерно N^2 бит. Конечно, ограничения задачи становятся слегка другими, но O(N)<O(N^2).


          1. Zealint
            29.03.2016 13:17
            #8827530

            При чём тут O(N^2)? В решении с 32-мя счётчиками будет один проход по циклу. Имеем те же O(N) битовых операций и O(1) памяти, в виде 32-х чисел размером 32 бита. Ну, плюс пара служебных переменных.


            1. Mrrl
              29.03.2016 13:35
              #8827558

              А в случае 16384-битных слов? Всё равно 32 счётчика?
              Правда, я не уверен, что решение с x^3 вообще работает.


              1. Zealint
                29.03.2016 13:58
                #8827608

                Я же напомнил выше, что в задаче чётко указан размер слова — 32 бита. В случае K-битных слов по любому решение будет зависеть от K, хотя бы потому, что нужно как-то это слово считать в память, тут не важно, делаем мы xor или сумму в конечных полях. И всё равно я не вижу тут O(N^2).


            1. ZyXI
              29.03.2016 14:00
              #8827614

              Судя по сообщению Mrrl под N имел ввиду разрядность числа, а не то, что указано в условии. Т.е. если считать разрядность числа в задаче переменной и равной b, то будет O(Nb) битовых операций и O(b?) памяти в случае с b счётчиками и O(b) памяти для его предложения.
              Чтобы не возникало недопонимания не нужно переназначать переменные из условия.


              1. Zealint
                29.03.2016 14:09
                #8827636

                Даже если так, то это уже обсуждение другой задачи. А в этой задаче размер слова чётко обозначен, и это с практической точки зрения даёт надежду на вполне эффективный алгоритм. Менять условия или пытаться решить более общую задачу вместо исходной — это не всегда хорошая идея. А в случае жёстких требований на время работы даже плохая. Не вижу также смысла пытаться ставить в качестве аргумента теоретическое время работы через символ "O" (который обозначает время для b->oo), которое никакого отношения к реальности обычно не имеет, особенно при малых значениях этого b.


        1. halyavin
          29.03.2016 21:04
          #8828486

          Очевидно, что подразумевается, что размер чисел равен машинному слову. Я не вижу другого разумного способа формализовать задачу. В стандартной модели вычислений, операции над машинными словами выполняются за O(1) и одно машинное слово занимает O(1) памяти.


          1. Zealint
            29.03.2016 21:24
            #8828528

            Ну так и я тоже не вижу никаких теоретических отличий между Вашими переменными "x" и "y" в конечном поле (по какому-то модулю, явно зависящему от размера слова), и набором переменных из решения с xor, размер которых будет в точности совпадать с размером слова, потому что размер слова не стремится к бесконечности и потому что в условиях задачи (некорректно поставленной) указано, что память не должна зависеть от размера массива, а будет ли она квадратичной или линейной по числу бит в слове, не важно. Что же касается практической эффективности обоих решений, то это тоже большой вопрос, что будет быстрее — 32 xor'a или вычисления кубов по модулю. Хотя я, конечно, не буду спорить о том, что любые правильные методы сами по себе заслуживают внимания и каждый из них по-своему хорош.


            1. halyavin
              29.03.2016 22:38
              #8828714

              Чтобы N стремился к бесконечности, битность чисел тоже должна стремиться к бесконечности. Даже в варианте где разрешены повторения парных чисел, очень странно указать 32 бита и не подразумевать, что числа имеют размер машинного слова. Тогда уж надо указывать 30 бит или 50 бит (компьютеры давно уже 64-битные, а это самое круглое число меньше 64).
              Некорректно поставленная задача означает лишь то, что ее нужно преобразовать в корректно поставленную наиболее естественным способом, используя общепринятые умолчания. После чего решить. При объяснении решения, в зависимости от обратной реакции вопрошающего, возможно преобразовать решение обратно. Подход требующий 32 слова в памяти не является решением получившейся корректно поставленной задачи, значит это не правильное решение. Если бы оно подразумевалось, нужно было бы писать в условии не O(1) памяти, а O(32) памяти. Ну или сразу писать корректную формулировку с переменной длиной машинного слова.
              PS Конечное поле тут не по модулю простого числа. Поле должно иметь характеристику 2, чтобы парные числа сокращались.


  1. astowork
    28.03.2016 18:27
    #8826450

    Задачке лет 5… это классика…
    Скрытый текстtype
    TMyElement= integer;
    PMyElement= ^TMyElement;
    TMyArray= array of TMyElement;
    TBitInfo= record
    Mask: TMyElement;
    Sum: TMyElement;
    end;

    const
    BitCount = SizeOf(TMyElement)*8;
    LastBitNo= BitCount-1;
    //поиск 0..2 непарных среди Count элементов массива, начиная с p
    procedure Find012(p: PMyElement; Count: integer; var Res: TMyArray);
    var
    bi: array[0..LastBitNo] of TBitInfo;
    t: TMyElement;
    q: PMyElement;
    i: integer;
    begin;
    if (p=nil) or (CountLastBitNo;
    end;
    end;
    end;
    end;


  1. pitrpg
    28.03.2016 18:28
    #8826466

    Вроде рабочий вариант решения, но с некоторыми ограничениями jsfiddle.net/669a3L45


  1. psplus2016
    28.03.2016 18:31
    #8826506

    Элементарно.
    Int main()
    {
    vector v = {1,2,3,3,1,2,4,7};
    //vector v = {1,2,7,4,1,2,3,3};
    //vector v = {1,2,3,4,1,2,3,7};
    int p = 0;
    int s = 0;
    int pp = 0;
    int ss = 0;
    for( size_t i = 0; i < v.size(); i++ )
    {
    if( i < (v.size() / 2) )
    p = p ^ v[i];
    else
    s = s ^ v[i];

    if( (i%2) == 0 )
    pp = pp ^ v[i];
    else
    ss = ss ^ v[i];
    }

    if( (p^pp) == p || (s^ss) == s )
    {
    cout


    1. psplus2016
      29.03.2016 00:09
      #8826896

      нифига не работает :) неверная тестовая последовательность была — привела к ложному "верному" результату.


  1. venco
    28.03.2016 19:56
    #8826656

    Моя попытка#include

    int main()
    {
    unsigned bit[32] = {}, all = 0, v, i;
    while ( std::cin >> v ) {
    all ^= v;
    for ( i = 0; i < 32; ++i ) {
    if ( v&(1


    1. venco
      29.03.2016 01:26
      #8826934

      Мда, тэги не прошли. И редактировать не могу.
      В общем, посмотрел другие решения, и эта идея уже была приведена несколько раз. Памяти требуется на 32-е xor суммы.


      1. ZyXI
        29.03.2016 01:38
        #8826944

        На 33. Плюс ещё куча вещей вроде памяти под исполняемый код и временные переменные вроде i и v, которые есть, но на которые всем (включая меня) при подсчёте памяти было наплевать.


        1. venco
          29.03.2016 01:56
          #8826952

          Ок, памяти требуется O(B^2) бит, где B-размер чисел в битах, остальное — меньшего порядка.
          А ещё общий xor можно собрать из побитовых xor-ов по диагонали.


  1. nikitadanilov
    29.03.2016 16:04
    #8827932

    Проще, наверное, показать код, чем описать:

    Скрытый текст
    static void findunique(int nr, uint32_t *a)
{
    uint32_t s[32][2] = {};
    int      i;
    int      j;
    for (i = 0; i < nr; ++i)
        for (j = 0; j < 32; ++j)
            s[j][!!(a[i] & (1 << j))] ^= a[i];
    for (j = 0; j < 32; ++j)
        if (s[j][0] != 0 && s[j][1] != 0)
            printf("%u %u\n", s[j][0], s[j][1]);
}


    1. nikitadanilov
      29.03.2016 16:24
      #8827978

      Update: все-таки опишу.
      Для каждого номера бита i, от 0 до 31, найдем сумму всех элементов массива, у которых i-й бит установлен (s[i][1]) и сумму элементов, у которых i-й бит не установлен (s[i][0]), все суммы по модулю 2. Всякий парный элемент участвует точно в тех же суммах, что и его пара и, таким образом, общий вклад от пары во всякой сумме равен 0.
      Предположим, сначала, что непарные элементы A и В отличны от нуля. Тогда отличны от нуля только те суммы s[i][j], в которых участвует один или оба непарных элемента. Но непарные элементы отличаются хотя бы одним битом (иначе они были бы парой) k, тогда один из них равен s[k][0], а другой — s[k][1].
      Если же один из непарных элементов равен нулю, то для любого k, s[k][0] и s[k][1] и дают искомые числа.