Знайти наступне число з такою ж кількістю встановлених бітів

Задача

Для цілого числа знайти найближче до нього більше число в якому така сама кількість встановлених в 1 бітів.

Рішення 1

Спочатку знайдемо (зправа наліво) перший нульовий біт який можна встановити в 1. Щоб число було більше знаходимо перший нульовий біт який йде за першою одиницею чи групою одиниць.

Встановлюємо знайдений біт в 1, а попередній ненульовий біт в 1. Далі треба зсунути усі попередні ненульові біти до самого початку.

 

unsigned get_next_n(unsigned n) { if (n == 0) return 0; unsigned idx = 0, bits = 0; // find 1st 1 while ((n & (1 << idx)) == 0) ++idx; // find 1st 0 after 1 while (n & (1 << idx)) ++idx, ++bits; // set 0 to 1 n |= 1 << idx; // set previous bits to minimal possible value - // all 1s at the very beginning --bits; int zeroMask = ~((1 << idx) - 1); n &= zeroMask; int onesMask = (1 << bits) -1; n |= onesMask; return n; }

Для пошуку найближчого меншого числа з такою ж кількістю встановлених бітів міняємо всі умови на протилежні. Тобто знаходимо перший встановлений біт після першої групи нулів, міняємо його на 0, а усі інші встановлені біти зсовуємо справо до знайденої позиції.

unsigned get_prev_n(unsigned n) { if (n < 2) return 0; unsigned idx = 0, bits = 0; // find 1st 0 while (n & (1 << idx)) ++idx, ++bits; // find 1st 1 after 0 while ((n & (1 << idx)) == 0) ++idx; // set 1 to 0 n &= ~(1 << idx); // set previous bits to maximal possible value - // all 1s right aligned at idx position ++bits; int zeroMask = ~((1 << idx) - 1); n &= zeroMask; int onesMask = ((1 << bits) - 1) << (idx - bits); n |= onesMask; return n; }

Рішення 2

Більш складне рішення для розуміння якого треба знати як представлені у двійковому вигляді від’ємні числа.

Візьмемо для прикладу число x = 76. Також представимо що усе знакове число у нас (для простоти) є однобайтним.

x = 01000110

Від’ємні числа представлені так – усі байти інфертовано плюс одиниця. Таким чином –1 преставлено як 11111111, –2 – 11111110 і так далі.

-x = 10111010

Бачимо що у x та –x співпадають лише перші ненульові біти. Отже можемо виділити цей біт:

x & –x = 00000010

Якщо до оригінального числа додати цей перший ненульовий біт то встановимо в одиницю перший нульовий біт що йде після першої одиниці (чи групи одиниць), а всі молодші біти встановимо в 0. Це буде ліва частина числа:

x + (x & –x) = 01001000

Тепер, якщо порівняти оригінальне число і отриманий результат бачимо що неспівпадають молодші біти. Можемо виділити лише їх:

x ^ (x + (x & –x)) = 00001110

Ці біти треба зсунути до самого початку числа і прибрати один зайвий. Отримуємо праву частину числа:

(x ^ (x + (x & –x))) >> 2) / (x & –x) = 00000001

Об’єднуємо ліву і праву частини:

((x ^ (x + (x & –x))) >> 2) / (x & –x)) | (x + (x & –x)) = 01001001

В коді це виглядатиме так:

unsigned get_next_n(unsigned n) { unsigned firstBit = n & -n; unsigned leftPart = n + firstBit; unsigned rightPart = ((n ^ leftPart) >> 2) / firstBit; return leftPart | rightPart }

 

Пояснення цього метолу зі слайдами тут – http://www.slideshare.net/gkumar007/bits-next-higher-presentation

Скопіювати біти одного числа в інше

Задача

Дано два 32-розрядних числа M та N, а також позиції i та j. Розмістити значення N у бітах від i до j числа M.

Ріщення

Побудуємо маску яка обнулить біти від i до j 32-х розрядного чила, після чого обнуломо відповідні біти в M і скопіюємо в них N:

int max = ~0; // усі біти встановимо в 1 // усе зправа від j встановимо в 0 int left = max - ((1 << j) - 1); // усе зліва від i встановимо в 0 int right = (1 << i) - 1; // у масці біти від i до j встановлені у 0, всі інші - в 1 int mask = left | right; // обнуляємо біти в M M &= mask; // копіюємо біти з N в M M |= N << i;

Визначити чи є одне дерево піддеревом іншого

Задача

Дано два дерева. Перше має дуже великий розмір (міліони елементів), інше – менший (сотні елементів). Треба написати функцію яка буде визначати чи є менше дерево піддеревом більшого.

Рішення 1

Для кожного елемента більшого дерева що містить значення еквівалентне значенню коріневого елемента меншого дерева перевіримо чи всі інші елементи також ідентичні.

 

// визначити чи дерева ідентичні bool match_tree(tree * r1, tree *r2) { if (r1 == NULL && r2 == NULL) return true; if (r1 == NULL || r2 == NULL) return false; if (r1->val != r2->val) return false; return match_tree(r1->left, r2->left) && match_tree(r1->right, r2->right); } // визначити чи другий параметр є піддеревом першого bool is_sub_tree(tree *r1, tree *r2) { if (!r2) return true; if (!r1) return false; if (r1->val == r2->val) return match_tree(r1, r2); return is_sub_tree(r1->left, r2) || is_sub_tree(r1->right, r2); }

Рішення 2

Можна для обох дерев побудувати рядок із значень їх елементів у порядку обхода inplace (лівий під-елемент->батьківський елемент->правий під-елемент). Після цього перевірити чи рядок для другого дерева є підрядком для першого дерева.

Знайти загального предка для двух вузлів дерева

Задача

Написати функцію яка для вказаного дерева і двох його елементів знаходить найблищого до цих елементів предка.

Дерево не є бінарним деревом пошуку.

Рішення

Для поточного елемента дерева (починаємо з корня) перевіряємо чи елементи обоє знаходяться у лівому/правому піддереві і якщо так то рекурсивно продовжуємо пошук у відповідному піддереві. Інакше поточний елемент є предком.

bool covers(tree *root, tree *p) { if (!root) return false; if (root == p) return true; return covers(root->left, p) || covers(root->right, p); } tree* common_ancestor(tree *root, tree *p, tree *q) { if (covers(root->left, p) && covers(root->left, q)) return common_ancestor(root->left, p, q); if (covers(root->right, p) && covers(root->right, q)) return common_ancestor(root->right, p, q); return root; }

Знайти k-тий по порядку елемент у двох відсортованих масивах

Задача

Написати функцію яка приймає два відсортовані масиви цілих чисел з унікальними значеннями і знайти k-тий по порядку елемент.

Зробити це треба швидше ніж за лінійний час.

Рішення

Якщо просто мати по індексу на масив і пересувати їх на найменший елемент то усього нам знадобиться k ітерацій.

Так само якщо ми спробуємо злити масиви то не вдасться зробити це швидше ніж за лінійнипй час.

Якщо ж скористатися бінарним пошуком то загальна складність становитиме O(lg M + lg N), де M та N розміри вхідних масивів.

Робимо ми це так:

  1. будуємо індекси i та j такі що i + j == k – 1. Наприклад ділимо відрізки навпіл.
  2. якщо B[j-1] < A[i] < B[j] то A[j] є результатом пошуку
  3. якщо A[i-1] < B[j] < A[i] то результатом буде B[j]
  4. модифікуємо індекси таким чином:
    1. якщо A[i] < B[j] то:
      1. якщо B[j] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в A
      2. інакше пересуваємо j на половину масиву вліво, і рівно на стільки ж позицій пересуваємо i (для того щоб їх сума дорівнювала k)
    2. Робимо схожі перевірки:
      1. якщо A[i] є останнім елементом у масиві то значення яке ми шукаємо знаходиться в B
      2. інакше пересуваємо i на половину масиву вліво, і рівно на стільки ж позицій пересуваємо j
  5. повертаємося до кроку 2.

Код на gist:

Повернути наступний елемент у дереві

Задача

Написати функцію яка приймає вузол дерева і повертає наступний по порядку елемент. Кожен вузол має посилання на батьківський елемент.

Рішення

Обхід дерева з трьох елементів здійснюється по порядку правий-батьківський-лівий. Самим першим елементом відповідно має бути самий лівий під-елемент.

Якщо поточний елемент має правий дочірний елемент то повернемо самий лівий елемент правого під-елементу.

Інакше якщо поточний елемент є лівим під-елементом батьківського елементу то повертаємо батьківський елемент, а інакше робимо батьківський елемент поточним і продовжуємо йти вгору.

void next_tree_node(tree_item *t) { tree_item *result = NULL; if (t) { if (t->right) { for (t = t->right; t->left; t = t->left); result = t; } else { for (tree_item *parent = t->parent; parent; t = parent, parent = parent->parent) { if (parent->left = t) { result = parent; break; } } } } return result; }

Знайти підмасив з найбільшою сумою елементів

Задача

Дано масив цілих чисел. Треба знайти підмасив елементів з найбільшою сумою – тобто знайти і суму і індекси.

Додаткове зауваження. В принципі це доволі відома задача і в мережі можна знайти безліч рішень для неї, наприклад – http://sites.google.com/site/computationalthinking/kadanealgorithm, або http://www.algorithmist.com/index.php/Kadane’s_Algorithm. Але є одна річ на яку треба звернути увагу – усі елементи вхідного масиву можуть бути від’ємними. А цього якраз усі ті наведені реалізації і не враховують.

Тобто треба не лише в масиві { 10, –1, –1, 18, –20, 30 } знайти виділений підмасив, але і в такому як  { –8, –2, –10 } знайти підмасив з одного елемента (-2).

Рішення

void find_the_biggest_subarray( int *a, size_t n, long int &sum, size_t &start, size_t &end) { sum = LONG_MIN; size_t curStart = start = end = 0; if (!a || n == 0) return; long curSum = sum = a[0]; for (size_t i = 1; i < n; ++i) { if (curSum < 0 && a[i] > curSum) { curSum = a[i]; curStart = i; } else { curSum += a[i]; } if (curSum > sum) { sum = curSum; start = curStart; end = i; } } }

Знайти елемент що повторюється у масиві унікальних значень

Задача

У масиві з N елементів присутні усі елементи від 1 до N, але один з них продубльовано. Треба знайти цей елемент за лінійний час без використання додаткової пам’яті.

Рішення

Рішення полягає в тому щоб кожен елемент помістити в ту позицію в масиві яка дорівнює його значенню. Як тільки знайдемо елемент позиція якого вже зайнята таким самим значенням ми знайшли дублікат.

Для кожного елемента масиву з індексом і виконаємо наступні дії:

  1. Беремо поточний елемент x = a[i]
  2. Якщо x == i то збільшити і та повернитуся до кроку 1.
  3. Якщо  a[x] == x то ми знайшли елемент який дублюється, інакше обміняти місцями значення a[i] та a[x] і повернутися до кроку і.
int find_duplicated_item(int*a, size_t n) 
{ 
    int result =-1, x =0; 
    for (size_t i =0; i < n; ) 
    { 
        if (a[i] != i +1) 
        { 
            x = a[i]; 
            
            if (a[x] == x) 
            { 
                result = x; 
                break; 
            } 
            
            a[i] = a[x]; 
            a[x] = x; 
        } 
        else ++i; 
    } 
}

Розмір групи та імовірність народження більша за 0.5

Задача

Якого розміру має бути група людей щоб імовірність народження хоч одного з неї в ту саму дати що народилися і ви (лише ісяць і число) складала не менше 50%?

Рішення

Для тих хто як і я математикою і теорією імовірності користувався останній раз в інституті/університеті спробую роз’яснити детально.

Для однієї випадкової людини імовірність народження в певну дату року складає 1/365. Позначимо її як p. Відповідность імовірність народження в будь яку іншу дату для тієї ж людини складає 1-p.

Тепер для двох людей складемо таку табличку:

А народився в певну дату

Б народився в певну дату

Імовірність того що дві ці події трапляться одночасно

ні так (1-p)*p
так ні p*(1-p)
так так p*p
ні ні (1-p)2

 

Щоб визначити імовірність народження в певну дату N людей треба скласти всі імовірності усих комбінацій крім тих де ніхто не народився у вказану дату. Або можна зробити простіше і взяти імовірність того що ніхто не народився у вказану дату – вона буде складати (1-p)n. Відповідно імовірність того що хоч хтось з N людей народився у вказану дату складатиме 1-(1-p)n.

Тепер треба знайти чому ж дорівнює n у рівнянні 1-(1-p)n=0.5

Як ми пам’ятаємо (якщо пам’ятаємо) функцією зворотньою ступеню є логарифм. Тому можемо записати так:

image

А як ми знаємо при маленьких значеннях p запис ln(1-p) можна спростити до –p.

Значення ln 0.5 можна знайти у таблицях (наприклад тут – http://www.piclist.com/images/www/hobby_elec/e_logarithm.htm).

Отже маємо:

image

Отже наша відповідь така – для того щоб імовірність що у випадковій групі людей є хоч хтось з такою самою датою народження як і у вас розмір групи має складати не менше ніж 252 людини.