检查一个整数是否是另一个整数幂

Question

这是一个采访问题:"给定2个整数x和y,检查x是否是y的整数幂"(例如,对于x = 8和y = 2,答案是"真",对于x = 10和y = 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