Минимум сравнений, необходимых для нахождения единственного более тяжелого шара из N шаров

Даны N (N > 1) шаров и весовой балансировочный станок. Имеются N-1 шаров одинакового веса, и один из них тяжелее остальных. Задача состоит в том, чтобы найти минимальное количество взвешиваний, необходимое для нахождения более тяжелого шара, при котором каждый раз можно взвешивать любое количество шаров.

Примечание. Балансировочная машина может определить относительный вес, а не абсолютный вес, т. е. вес одного мяча по отношению к другому.

Примеры:

Input: N = 5
Output: 2
Explanation: Divide the balls into 2+2+1 parts. Weigh the groups with 2 balls. 
If they weigh the same the other is having a different weight. 
Otherwise, take the group with greater weight(as it has the required ball) and 
measure them one vs one(2 times measuring case).

Input: N = 9
Output: 2

Наивный подход: Решение основано на следующем наблюдении.

• Любое количество шаров (N) можно разделить на 3 группы с примерно равным количеством шаров, и два из них можно взвешивать одновременно.
  • Теперь, если какой -либо из них тяжелее другого, то более тяжелый шар находится в этой группе .
  • В противном случае он находится в невзвешенной группе.
    • Теперь снова эту группу можно разделить на 3 подгруппы , и так далее.
• Итак, это дает рекурсивную функцию.

Поэтому используйте рекурсивную функцию, где N делится на 3 на каждом шаге, а рекурсия теперь вызывается при максимальном значении N/3.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O (log (N))
Вспомогательное пространство: O(1)

Эффективный подход: из приведенного выше подхода ясно видно, что он аналогичен нахождению показателя степени 3 , который равен или больше, чем N . Который можно вычислить с помощью логарифма .

Временная сложность: O(1)
Вспомогательное пространство: O(1)