Нужно ускорить java метод

Question

В начале добавил условие задачи, чтобы было проще понять суть.

Мой метод рабочий! Но, по условиям нужно сделать его гораздо быстрее.
Eсли есть возможность, помогите пожалуйста, очень интересно разобраться в вопросе.

Мощностью чётного числа является количество последовательных делений этого числа на 2, пока не получится нечётное число, начиная с чётного числа n.

Например, если n = 12, то

12 / 2 = 6 6 / 2 = 3
То есть мы разделили подряд 2 раза, получив 3, поэтому мощность 12 равна 2.

Если n = 16, то

16 / 2 = 8 8 / 2 = 4 4 / 2 = 2 2 / 2 = 1
разделили подряд 4 раза, получили 1, мощность 16 равна 4

Задание
Для заданного отрезка [n, m], вернуть чётное число с наибольшей мощностью. Если существует несколько решений, вернуть наименьшее чётное число с наибольшей мощностью.

Заметим, что программы должны завершиться в течение отведённого времени сервера; наивное решение вероятно превысит лимит времени.

Ограничения 1 <= n < m <= INT_MAX

Примеры
[1, 2] --> 2 # 1 имеет мощность 0, 2 имеет мощность 1
[5, 10] --> 8 # 5, 7, 9 имеют мощность 0; 6, 10 имеют мощность 1; 8 имеет мощность 3
[48, 56] --> 48

public class StrongestEvenNumber {
    
    public static int strongestEven(int n, int m) {
        int[] nmArray = new int[m - n + 1];
        int[] nmPowerOfNumbers = new int[m - n + 1];
        int l = 0;
        for (int i = n; i <= m; i++) {
            nmArray[l] = i;
            int k = i;
            int powerOfNumber = 0;
            while (k % 2 == 0) {
                k = k/2;
                powerOfNumber++;
            } 
            if (i % 2 == 0)
                nmPowerOfNumbers[l] = powerOfNumber;
            l++;
        } 
        int theMostPowerfulIndex = 0;
        int theMosPowerfulOfNumber = nmPowerOfNumbers[0];
        for (int i = 0; i < nmPowerOfNumbers.length - 1; i++) {
            if (theMosPowerfulOfNumber < nmPowerOfNumbers[i + 1]) {
                theMosPowerfulOfNumber = nmPowerOfNumbers[i + 1];
                theMostPowerfulIndex = i + 1;
            }
        } 
        return nmArray[theMostPowerfulIndex];
    } 
}

Answer 1

Одно из наивных решений: перебирать в цикле чётные числа и искать максимум замыкающих нулей при помощи метода Integer::numberOfTrailingZeros

При этом в качестве первоначального приближения можно попытаться отыскать наибольшую степень 2 в заданном диапазоне [n, m] либо циклом от 1 << 30 (2³⁰), либо при помощи логарифма.

Затем в цикле по мере обнаружения чисел с большей мощностью можно изменять приращение, следуя логике: если обнаружено число X с мощностью N, следующим числом с большей мощностью могут быть числа X + N, X + 2 * N, и т.д.

В примере с диапазоном [48, 56] мощность 48 составит 4 (кратно 16), соответственно, не нужно будет проверять числа, меньшие чем 48 + 16 - сразу выходим за пределы диапазона.

static int mostPowerful(int n, int m) {
    int p = 1 << (int)(Math.log(m) / Math.log(2));
    
    if (n <= p && p <= m) return p;
    
    int maxZero = 0;
    int minNum = 0;
    int delta = 2;
    for (int i = n + n % 2, k = m - m % 2; i <= k;) {
        p = Integer.numberOfTrailingZeros(i);
        if (p > maxZero) {
            maxZero = p;
            minNum = i;
            delta = 1 << p;
            // отладочный вывод, можно убрать/закомментировать
            System.out.println(p + "; i=" + i + "; delta=" + delta);
        }
        i += delta;
    }
    return minNum;
}

Тесты:

int[][] tests = {
    {1, 2},
    {5, 10},
    {35, 56},
    {77, 99},
    {62, 120}
};

for (int[] t : tests) {
    System.out.println(Arrays.toString(t) + " -> " + mostPowerful(t[0], t[1]));
}

Результаты:

[1, 2] -> 2
[5, 10] -> 8
2; i=36; delta=4
3; i=40; delta=8
4; i=48; delta=16
[35, 56] -> 48
1; i=78; delta=2
4; i=80; delta=16
5; i=96; delta=32
[77, 99] -> 96
[62, 120] -> 64

То есть, в случае попадания степени 2 в диапазон, сложность составляет O(1).

БЛОГ НА HUSL

Нужно ускорить java метод

Ответы (1 шт):