Мощность двух целых чисел


Задачи:

Дано положительное целое число, которое помещается в \32 $\$ разрядное целое число, найти если оно может быть выражено как \долларов\^П$ где \$П > 1\$ и $\А > 0\$. A и P оба должны быть целыми.

Пример

Входной сигнал : 4
Вывод : Правда
как \2$^2 = 4\$.

Мой подход:

public class Solution {
    public int isPower(int A) {
        int exp, base;

        if( A == 1)
            return 1;

        if( A%2 == 0)
            {
                for( int i = 2; i < A; i+= 2 )
                  {
                        double variable = Math.log(A) / Math.log(i);
                        double formatted = Double.parseDouble(String.format( "%.6f", variable));

                        if((formatted== Math.floor(formatted)) && !Double.isInfinite(formatted))
                            return 1;
                  }
                return 0;    
            }

        else
            {
                for( int i = 3; i < A/2; i+= 2 )
                  {
                       double variable = Math.log(A) / Math.log(i);
                       double formatted = Double.parseDouble(String.format( "%.6f", variable));

                        if((formatted== Math.floor(formatted)) && !Double.isInfinite(formatted))
                           return 1;
                  }
                return 0;    
            }        

    }
}

У меня есть следующие вопросы касаемо выше код:

  1. Есть ли лучший способ решить этот вопрос?

  2. Как я могу оптимизировать время и сложность пространства решений?



Комментарии
4 ответа

Точность

С плавающей точкой аппроксимации не является приемлемой заменой для целочисленной арифметики! В противном случае, вы в конечном итоге с ошибками, как и все остальное фальшивка контрпример Великой теоремы Ферма.

Homer's false disproof of Fermat's Last Theorem

Как это применить к вашему коду? Рассмотрим isPower(2147483647). Ваш код дает 1потому что он думает, что 463412 ≈ 2147483647. На самом деле, 463412 = 2147488281, и правильный ответ - "ложь", так как 2147483647 премьер.

Фильтрация ряд через doubleStringdouble обратного преобразования является особенно вопиющим.

Именования

Старайтесь выбирать имена переменных, которые согласуются с номенклатурой в вызов. Ваш variable действительно п; ваш i соответствует собой; ваш A должен называться что-то совсем другое — возможно n.

Предлагаемое решение

Подсчитайте количество каждого основного фактора Н происходит. Вы должны быть в состоянии разделить эти факторы на равные группы, с одиноким факторов осталось.

import java.util.PrimitiveIterator;
import java.util.stream.IntStream;

public class Solution {
/**
* Calculates the GCD of two numbers using the Euclidean Algorithm.
*/
private static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}

public boolean isPower(int n) {
PrimitiveIterator.OfInt factors =
IntStream.concat(IntStream.of(2), IntStream.iterate(3, i -> i + 2))
.iterator();

// Count the number of times each prime factor occurs
IntStream.Builder exponents = IntStream.builder();
int f, e;
do {
f = factors.nextInt();
for (e = 0; n % f == 0; e++) {
n /= f;
}
if (e > 0) {
exponents.add(e);
}
} while (f < n);

// Try to segregate the factors into equal groups with no loners.
// If there is no GCD, then n was 1, so a=1, p=2 would work.
int p = exponents.build().reduce(Solution::gcd).orElse(2);
return p > 1;
}
}

5
ответ дан 27 февраля 2018 в 03:02 Источник Поделиться


  1. Задача определяет выходные данные функции true или false. Ява имеет boolean примитивно моделировать именно это. Ваш метод должен возвращать boolean не int что "значит" true когда это не 0 (как в случае с).

  2. Это общепризнанная лучшая практика в Java для определения каждой переменной (и член) на отдельной строке. exp и base должны быть заявлены в отдельных строках.

  3. Это легче на ваш мозг, чтобы отслеживать вещей, если вы используете их непосредственно после того, как вы ввели их. Что обычно называют "объявив переменные как можно ближе к их использования".

  4. Подавляющее большинство Ява конвенций гласит, что бинарные и тернарные операторы должны иметь пробелы вокруг операторов. В коде, который применяется в +=, % и иногда ==. Как правило, форматирование, кажется, старается сопоставляя некоторые стандартные, но не вполне согласуются, что подтверждается / имея интервал при расчете variableно не тогда, когда внутри для петля голова...
    Прежде всего вы должны стремиться быть последовательным с форматированием кода. Что делает его более удобным для чтения.

  5. Большинство конвенций Ява предпочитают открывающие фигурные скобки на той же строке, как заблокировать вступительное заявление. Что означает то же самое общеукрепляющее стиль как метод определения распространяется на if, else и for заявления.
    В дополнение к этому я настоятельно рекомендую устанавливать скобки везде, где это возможно.

  6. И наконец: для петель в if (A % 2 == 0) и else только отличаться по их первоначальной стоимости. Помимо того, что они такие же. Почему вы выбрали для использования шаг-размером два с начинается отличающихся на единицу, когда вы могли бы точно также повторяется с шагом 1?

1
ответ дан 26 февраля 2018 в 10:02 Источник Поделиться

Для данного числа N, мы делаем круг над потенциальной базы номера, и вычислить показатель степени П, проверив, является ли это число. Таким образом, вам придется перебрать много цифр.

Если у вас наоборот, с петлей на потенциальных экспонентов П, рассчитав соответствующие базы и проверки на целочисленное значение, вам нужно только перебрать от П=2 до п=30.

Я не проверить, если ваш код работает - у меня есть сомнения, особенно с "проверка на целое число" части.


Несколько замечаний по вашему стилю кодирования:

Ваш способ isPower() Это означало, чтобы проверить, если данное число можно представить, как власти^П. вместо int вы должны вернуть boolean (true или false вместо 1 или 0).

Именование классов, методов, полей, переменных и т. д. имеет решающее значение для удобочитаемости кода. Они должны отражать, что они представляют. Так, isPower - хорошее название для метода, который проверяет, является ли число-это мощность. Но такие имена, как variable не поможет. Имена exp и base хороший выбор, но вы только объявлять о них и не использовать их (любая приличная IDE будет помечать их как неиспользуемые). Одну букву имена следует избегать, насколько это возможно (за исключением цикла переменные, такие как i, jили k).

Есть правила именования в Java, особенно переменные всегда должны начинаться со строчной буквы. Долгосрочный разработчиков Java будут автоматически понимать все, что начинается с заглавной, как имя класса, и имеют трудное время, если в коде, конвенций не применяются.

Ваши отступы и размещение брекетов является уникальным. После обычных стиль делает его легче читать ваш код и не тратить так много места (даже простой класс, представленные здесь линии слишком широк, чтобы поместиться в пространство на этом сайте).

Код

    if( A == 1)
return 1;

не окружающие зависимого заявление с оттяжками, риск обслуживания. Представьте, что кто-то хочет добавить сюда еще одно заявление:

    if( A == 1)
log.info("found a solution");
return 1;

Это выглядит хорошо на первый взгляд, но эффективно это:

    if( A == 1) {
log.info("found a solution");
}
return 1;

Не то, что вы хотите, не так ли? Поэтому, я рекомендую всегда использовать фигурные скобки.

Писать комментарии javadoc по крайней мере для всех публичных классов и методов.

После переименования, комментирование и форматирование кода (но сохраняя свой алгоритм), мы получим:

/**
* Solution to the <a href=https://www.interviewbit.com/problems/power-of-two-integers/>
* Power of Two Integers</a> problem.
*
* @author your name
*/
public class Solution {

/**
* Check if <code>power
могут быть представлены как A^P
* С и П целые числа и P больше 1.
* @парам мощность количество тестируемых
* @возвращает true, если power могут быть представлены как A^P
*/
общественная логическое isPower(инт мощность) {
если (власти == 1) {
возвратите True;
}

если (мощность % 2 == 0) {
для (int основание = 2; базы < мощность; база += 2) {
двойной EXP = математика.журнал(мощность) / математика.журнал(база);
двойной formattedExp = двойной.parseDouble(строка.формат("%.6Ф", эксп));

если ((formattedExp == математика.пол(formattedExp)) && !Двойной.isInfinite(formattedExp)) {
возвратите True;
}
}
возвращает false;

} еще {
для (int базы = 3; базы < мощность / 2; базовый += 2) {
двойной EXP = математика.журнал(мощность) / математика.журнал(база);
двойной formattedExp = двойной.parseDouble(строка.формат("%.6Ф", эксп));

если ((formattedExp == математика.пол(formattedExp)) && !Двойной.isInfinite(formattedExp)) {
возвратите True;
}
}
возвращает false;
}
}
}

0
ответ дан 26 февраля 2018 в 08:02 Источник Поделиться

Есть несколько веских доводов, касающихся стиля программирования и арифметики с плавающей точкой, но я хочу сосредоточиться на улучшении сложность решения. Из моих экспериментов, кажется, что проще лучше. Просто зацикливание над базами и экспонентам дает результат, который >20 раз быстрее, чем предыдущие ответы, размещенные здесь.

public class Solution {

public static int pow2(int a, int b) {
int re = 1;
while (b > 0) {
if ((b & 1) == 1) {
re *= a;
}
b >>= 1;
a *= a;
}
return re;
}

public boolean isPower(int n) {
if (n < 4) {
return n == 1;
}

for (int a = 2; a < Math.sqrt(n)+1; a++) {
if (n % a*a == 0) {
for (int p = (int) (Math.log(n)/Math.log(a)); p < 32; p++) {
int result = pow2(a, p);
if (result == n) {
return true;
}
if (result > n) {
break;
}
}
}
}
return false;
}
}

Раскрытие информации: я скопировал pow2 функции здесь.

Объяснение: так как вход был положительным целым числом, мы сначала создали специальные чехлы для n<4. Для любого другого значения n, проверить каждое значение a который является подходящим кандидатом. Там нет необходимости, чтобы проверить за sqrt(n)потому что самый низкий показатель p=2.

С некоторым математике, вы можете выяснить, что с учетом базы a, показатель степени п должен быть примерно log(n)/log(a). Так n помещается в 32-разрядное целое число, мы знаем, что p<32.

Тогда мы просто вычислить a^p и проверить, если он равен n. Просто. Этот код выдает одинаковые результаты для всех значений n менее 100000 (вот как далеко я проверял) по сравнению с предыдущими решениями в этой теме.

Возможные будущие усовершенствования: удалить всех арифметических операциях с плавающей запятой и вместо того, чтобы использовать бит-операции сдвига для аппроксимации логарифма, а не особый случай, чтобы увидеть, если n имеет только один бит (например, 0b00100000), из которого следует, что она является властью 2.

Редактировать: дополнительное ускорение

После некоторых исследований, я пришел к выводу, что изменение порядка поиска будет заставить ее работать быстрее. Поскольку мы знаем, что 1<p<lg(n)+1мы можем попробовать все эти значения, и выполнить бинарный поиск по значение a.

public boolean isPower(int n) {
if (n < 4) {
return n == 1;
}

int maxExponent = 0;
int tempN = n;
while (tempN > 0) {
maxExponent++;
tempN >>= 1;
}
int low_a;
int high_a;
int temp_a;
int result;

for (int p = 2; p < maxExponent+1; p++) {

low_a = 1;
high_a = 1<<(maxExponent/p+1);

while (high_a-low_a > 1) {

temp_a = (low_a+high_a)/2;
result = pow2(temp_a, p);

if (result == n) {
return true;
}
if (result < n) {
low_a = temp_a;
} else {
high_a = temp_a;
}
}
}
return false;
}

Некоторые из них включают показатели:

Time to calculate isPower for every number between 1 and 10^5:
200_success' solution: 2.769842086 seconds
My previous solution: 0.108119151 seconds
My new solution: 0.034731273 seconds

Time to calculate isPower for every number between 1 and 10^6:
200_success' solution: ~30 seconds
My previous solution: 2.833582944 seconds
My new solution: 0.4383110970 seconds

Time to calculate isPower for every number between 10^9 and 10^9+10^4:
200_success' solution: not included
My previous solution: 1.3411200 seconds
My new solution: 0.014713117 seconds

Из этого теста мы можем увидеть, что новый алгоритм значительно быстрее при больших значениях nбудучи почти в 100 раз быстрее в последние эталоном.

0
ответ дан 28 февраля 2018 в 12:02 Источник Поделиться