Google Foobar — «Отвлеките тренеров»

ВОПРОС:

Вы будете организовывать одновременные поединки по борьбе на большом пальце. В каждом матче два тренера будут сражаться в паре для борьбы на большом пальце. Тренер с меньшим количеством бананов поставит все свои бананы, а другой тренер сделает ставку. Победитель получит все бананы по ставке. Вы не можете сочетать кроссовки с одинаковым количеством бананов (вскоре вы поймете, почему). Вы достаточно знакомы с психологией тренера, чтобы знать, что тот, у кого больше бананов, всегда становится слишком самоуверенным и проигрывает. Как только матч начнется, пара тренеров продолжит борьбу на пальцах и обменивается бананами, пока у них обоих не будет одинаковое количество бананов. Как только это произойдет, они оба потеряют интерес и вернутся к надзору за рабочими-кроликами, а вы не хотите, чтобы ЭТО случилось!

Например, если два тренера, которые были спарены, начали с 3 и 5 бананов, после первого раунда борьбы на большом пальце у них будет 6 и 2 (тот, у кого 3 банана, выигрывает и получает 3 банана от проигравшего). После второго раунда у них будет 4 и 4 (тот, у кого 6 бананов, проигрывает 2 банана). На этом они останавливаются и возвращаются к тренировкам кроликов.

Чем все это полезно, чтобы отвлечь дрессировщиков кроликов? Обратите внимание: если тренеры начали с 1 и 4 бананов, то они продолжают борьбу на большом пальце! 1, 4 -> 2, 3 -> 4, 1 -> 3, 2 -> 1, 4 и так далее.

Теперь ваш план ясен. Вы должны соединить кроссовки таким образом, чтобы максимальное количество тренажеров входило в бесконечный цикл борьбы на большом пальце!

Напишите функциональное решение (banana_list), которое, учитывая список положительных целых чисел, показывающих количество бананов, с которых начинает каждый тренажер, возвращает наименьшее возможное количество дрессировщиков кроликов, которые останутся наблюдать за рабочими. Элементом i списка будет количество бананов, с которых начинает тренировку i (считая с 0).

Количество трейнеров должно быть не менее 1 и не более 100, а количество бананов, с которых начинается каждый трейнер, будет положительным целым числом, не превышающим 1073741823 (т.е. 2 ^ 30 -1). Некоторые из них хранят МНОГО бананов.

— Кейсы Java —

Вход: solution.solution (1,1)

Выход: 2

Вход: Solution.solution ([1, 7, 3, 21, 13, 19])

Выход: 0

Мой подход:

Проверить НОД пары. Для повторяющихся циклов НОД никогда не меняется. Для завершающих последовательностей GCD удваивается на каждом шаге. Однако следует рассмотреть третий тип петель. У некоторых есть отрыв в последовательности, которая не повторяется, но в конечном итоге превращается в зацикленную последовательность. Для них GCD будет увеличивать каждый шаг для неповторяющегося отведения в части последовательности, а затем станет статическим для повторяющегося раздела. Так что просто протестировать первый и второй этап последовательности будет недостаточно.

Однако мы можем пойти дальше. Если какой-либо из НОД делит сумму пары на степень двойки, цикл завершается.

МОЙ КОД:

public class Solution {
    public static int gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
          return b;
        if (b == 0)
          return a;
      
        // base case
        if (a == b)
            return a;
      
        // a is greater
        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }
    
    static boolean isPowerOfTwo(int n)
    {
        if(n==0)
        return false;
     
    return (int)(Math.ceil((Math.log(n) / Math.log(2)))) == (int)(Math.floor(((Math.log(n) / Math.log(2)))));
    }
    public static int countpairs(int[] b) {
        int c=0;
        for(int i=0;i<b.length;i++) {
            for(int j=0;j<b.length;j++)
                c++;
        }
        return c;
    }
    public static int solution(int[] banana_list) {
        int[] b=banana_list;
        int count=countpairs(b);
        for(int i=0;i<b.length;i++) {
            for(int j=0;j<b.length;j++) {
                if(i==j) {}
                else {
                    int s=(b[i]+b[j])/gcd(b[i],b[j]);
                    if(isPowerOfTwo(s)==true)
                        count--;
                }
            }
        }
        if(count>b.length)
            return 0;
        
        return count;
    }
    
    public static void main(String[] args) {
        int a[]= {1,1};
        System.out.println("Minimum trainers: "+solution(a));
    }
}

Этот код проходит 2/5 тестовых случаев. Не работает в случае нечетного количества тренеров.

Рекурсия хороша только в том случае, если вы знаете ее глубину

Если у вас есть дерево с максимальной глубиной 100 или около того, рекурсия нормальна для его обхода. Но здесь можно получить миллион шагов рекурсии для глупого примера gcd (1,1000000). Измените его на петлю.

НОД можно вычислить быстрее, если вы измените вычитание по модулю

Поскольку (ab)% b === (a% b)% b, gcd сохраняется.

Степень двойки можно проверить с помощью побитовой логики

Вы можете попробовать сдвигать вправо, пока число не станет нечетным, и проверить, равно ли оно 1, это быстрее, чем ваше решение; но есть еще одна хитрость: x&(x-1)==0 только для степени 2.

Алгоритм

Вам вообще не нужен НОД. Только четное / нечетное. Если оба числа четные — разделите их на два. Если один четный, другой нечетный — прекращения не будет. Если оба нечетные — заставьте их драться и повторите процесс.