Проверьте, является ли одно целое число целой степенью другого

Question

Это вопрос для интервью : «Учитывая 2 целых числа x и y, проверьте, является ли x целой степенью y» (например, для x = 8 и y = 2 ответ «true» а для х = 10 и у = 2 «ложь»).

Очевидное решение:

int n = y; while(n < x) n *= y; return n == x

Теперь я думаю о том, как его улучшить.

Конечно, я могу проверить некоторые особые случаи: например, x и y должны быть нечетными или четными числами, то есть мы можем проверять младший значащий бит x и y. Однако мне интересно, смогу ли я улучшить сам алгоритм ядра.

Answer 1

Вы бы лучше несколько раз разделить y на x.В первый раз, когда вы получаете ненулевой остаток, вы знаете, что x не является целочисленной степенью y.

while (x%y == 0)  x = x / y
return x == 1

Это относится к вашей нечетной / четной точке на первой итерации.

Answer 2

Это означает, что log _y (x) должно быть целым числом . Не нужно никакой петли . в O (1) время

public class PowerTest {

    public static boolean isPower(int x, int y) {
        double d = Math.log(Math.abs(x)) / Math.log(Math.abs(y));

        if ((x > 0 && y > 0) || (x < 0 && y < 0)) {
            if (d == (int) d) {
                return true;
            } else {
                return false;
            }
        } else if (x > 0 && y < 0) {
            if ((int) d % 2 == 0) {
                return true;
            } else {
                return false;
            }
        } else {
            return false;
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        System.out.println(isPower(-32, -2));
        System.out.println(isPower(2, 8));
        System.out.println(isPower(8, 12));
        System.out.println(isPower(9, 9));
        System.out.println(isPower(-16, 2));
        System.out.println(isPower(-8, -2));
        System.out.println(isPower(16, -2));
        System.out.println(isPower(8, -2));
    }

}

Answer 3

Это ищет показатель степени в O (log N) шагах:

#define MAX_POWERS 100

int is_power(unsigned long x, unsigned long y) {
  int i;
  unsigned long powers[MAX_POWERS];
  unsigned long last;
  last = powers[0] = y;

  for (i = 1; last < x; i++) {
    last *= last; // note that last * last can overflow here!
    powers[i] = last;
  }
  while (x >= y) {
    unsigned long top = powers[--i];
    if (x >= top) {
      unsigned long x1 = x / top;
      if (x1 * top != x) return 0;
      x = x1;
    }
  }
  return (x == 1);
}

Отрицательные числа не обрабатываются этим кодом, но это может быть легко сделано с некоторым условным кодом, когда i = 1

Answer 4

    double a=8;
    double b=64;

    double n = Math.log(b)/Math.log(a);
    double e = Math.ceil(n);

    if((n/e) == 1){
        System.out.println("true");
    } else{
       System.out.println("false");
    }

Answer 5

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

#include <iostream>
#include <cmath>
using namespace std;

//x is the dividend, y the divisor.
bool isIntegerPower(int x, int y)
{
    int low = 0, high;
    int exp = 1;
    int val = y;
    //Loop by changing exponent in the powers of 2 and
    //Find out low and high exponents between which the required exponent lies.
    while(1)
    {
        val = pow((double)y, exp);
        if(val == x)
            return true;
        else if(val > x)
            break;
        low = exp;
        exp = exp * 2;
        high = exp;
    }
    //Use binary search to find out the actual integer exponent if exists
    //Otherwise, return false as no integer power.
    int mid = (low + high)/2;
    while(low < high)
    {
        val = pow((double)y, mid);
        if(val > x)
        {
            high = mid-1;
        }
        else if(val == x)
        {
            return true;
        }
        else if(val < x)
        {
            low = mid+1;
        }
        mid = (low + high)/2;
    }
    return false;
}

int main()
{
    cout<<isIntegerPower(1024,2);
}

Answer 6

Вот версия Python, которая объединяет идеи @salva и @Axn и модифицирована так, чтобы не генерировать никаких чисел, превышающих заданные, и использует только простое хранилище (читай, «нет списков») путем многократного разделения на интересующий номер:

def perfect_base(b, n):
    """Returns True if integer n can be expressed as b**e where
    n is a positive integer, else False."""

    assert b > 1 and n >= b and int(n) == n and int(b) == b

    # parity check
    if not b % 2:
        if n % 2:
            return False  # b,n is even,odd
        if b == 2:
            return n & (n - 1) == 0
        if not b & (b - 1) and n & (n - 1):
            return False  # b == 2**m but n != 2**M
    elif not n % 2:
        return False  # b,n is odd,even

    while n >= b:
        d = b
        while d <= n:
            n, r = divmod(n, d)
            if r:
                return False
            d *= d
    return n == 1

Answer 7

В случаях, когда y равно 2, существует быстрый подход, который устраняет необходимость в цикле.Этот подход может быть распространен на случаи, когда y - это некоторая большая степень 2.

Если x - это степень 2, двоичное представление x имеет один установленный бит.Существует довольно простой алгоритм поиска битов для подсчета битов в целых числах за O (log n), где n - это битовая ширина целого числа.Многие процессоры также имеют специализированные инструкции, которые могут обрабатывать это как одну операцию, примерно так же быстро, как (например) целочисленное отрицание.

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

Если этот бит является единственным битом, то (1 << pos) == x.Преимущество здесь в том, что если вы тестируете на степень 4, вы можете проверить на pos % 2 == 0 (один бит находится в четном положении).Тестируя на степень любой степени двойки, вы можете проверить на pos % (y >> 1) == 0.

В принципе, вы можете сделать что-то подобное для тестирования степеней 3 и степеней 3. Проблема в том, что вынужна машина, которая работает в базе 3, что маловероятно.Вы, конечно, можете проверить любое значение x, чтобы увидеть, имеет ли его представление в базе y одну ненулевую цифру, но вы будете выполнять больше работы, чем уже делаете.Вышеупомянутое использует тот факт, что компьютеры работают в двоичном формате.

Вероятно, не стоит делать в реальном мире, хотя.

Answer 8

Если подумать, не делай этого.Это не работает для отрицательных x и / или y. Обратите внимание, что все остальные представленные на данный момент ответы log также разбиты точно таким же образом.

Ниже приведено быстрое общее решение (на Java):

static boolean isPow(int x, int y) {
    int logyx = (int)(Math.log(x) / Math.log(y));
    return pow(y, logyx) == x || pow(y, logyx + 1) == x;
}

Где pow() - целочисленная функция возведения в степень, такая как следующее в Java:

static int pow(int a, int b) {
    return (int)Math.pow(a, b);
}

(Это работает из-за следующей гарантии, предоставляемой Math.pow: "Если обааргументы являются целыми числами, тогда результат в точности равен математическому результату возведения первого аргумента в степень второго аргумента ... ")

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

Answer 9

Я бы реализовал эту функцию следующим образом:

bool IsWholeNumberPower(int x, int y)
{
    double power = log(x)/log(y);
    return floor(power) == power;
}

Это не требует проверки внутри дельты, как это обычно происходит при сравнении с плавающей запятой, поскольку мы проверяем целые числа.

Answer 10

Предыдущие ответы верны, мне больше всего понравился ответ Павла. Это просто и чисто. Вот реализация Java того, что он предложил:

public static boolean isPowerOfaNumber(int baseOrg, int powerOrg) {
    double base = baseOrg;
    double power = powerOrg;

    while (base % power == 0)
        base = base / power;
    // return true if base is equal 1
    return base == 1;
}