Интересное задание codewars.com

[j0hnik]

6Ку
на входе массив вида [ 1, 8, 4, 4, 6, 1, 8 ] числа целые, от 1 до 2^31, в котором нужно найти уникальный элемент и вернуть его. массивы большие важна скорость.

https://www.codewars.com/kata/find-t...ain/javascript

findUnique([1, 8, 4, 4, 6, 1, 8]) //6;
findUnique([ 1234567 ]) //1234567;
findUnique([ 1, 4, 4, 5, 5, 3, 3, 2, 2 ])// 1;
findUnique([ 2, 2, 5, 5, 4, 3, 3, 1, 1 ])// 4;
findUnique([ 3, 5, 5, 4, 4, 3, 2, 2, 9 ])// 9;

[Alexandroppolus]

Мне больше нравится вариант с двумя уникальными числами.

j0hnik,
ты, кстати, не написал, что тут числа целые, от 0 до 2^31

[j0hnik]

Alexandroppolus,
дополнил

[Alexandroppolus]

https://www.codewars.com/kata/gerrymander-solver

Веселая задачка по мотивам этой их американской избирательной системы. Есть квадрат 5х5, в каждой ячейке по одному избирателю, 10 из них за тебя, 15 против, нет воздержавшихся. Надо разбить квадрат на 5 областей (по 5 избирателей в каждой области), чтобы одержать победу в трех областях. Области должны быть "связными", т.е. всю область можно обойти, только пересекая границы соседних ячеек в ней (соседние - значит имеют общую сторону).
Для какого-то расклада решения может не быть, тогда вернуть null

[j0hnik]

6к
простенькая, под чай.
Дан отсортированный массив целых чисел в котором нужно найти наименьший индекс который равен значению ( arr[index] == index )
если такого индекса нет, вернуть -1

Ваш алгоритм должен быть очень эффективным.

Примеры:
вход: [-8,0,2,5]
выход: 2, поскольку массив arr[2] == 2

вход: [-1,0,3,6]
выход: -1

для тестов будет использоваться
Стартовые (коротенькие массивы)
и для проверки производительности
массивы длинной 200 000
Количество испытаний: 1 000

https://www.codewars.com/kata/elemen...ain/javascript

[Alexandroppolus]

j0hnik,
опять забыл важное условие числа в массиве не повторяются, все разные

а в целом сразу понятно куда копать - двоичный (или даже интерполяционный) поиск, a[i] >= i - смотрим влево, a[i] < i - вправо

[j0hnik]

Alexandroppolus,
1 цикл находит нужную тысячу второй нужный индекс. и по скорости этого уже достаточно т.к 6к.

[рони]

поиск, a[i] >= i - смотрим влево, a[i] < i - вправо

function indexEqualsValue(a)
      {
        var max = a.length;
        var min = 0;
        var i;
        while (min != max) {
            i = Math.floor((max + min)/2);
            if (a[i] > i) max = i;
            else if (a[i] < i) min = i + 1;
            else if (i && a[i-1] == i-1) max = i;
            else return i
        }
            return -1
      }
      var i = indexEqualsValue([-8,0,2,5])
      alert(i);//2
      i = indexEqualsValue([-1,0,3,6])
      alert(i);//-1
      i = indexEqualsValue([0,1,2,3])
      alert(i);//0
      i = indexEqualsValue([-3,0,1,3,10])
      alert(i);//3

[j0hnik]

рони,
Хорошие решение

[j0hnik]

если кому интересно #112 пост
решение

function findUnique(numbers) {
  return numbers.reduce((a, b) => a ^ b);
}