32

This is an interview question: "Given 2 integers x and y, check if x is an integer power of y" (e.g. for x = 8 and y = 2 the answer is "true", and for x = 10 and y = 2 "false").

The obvious solution is:

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

Now I am thinking about how to improve it.

Of course, I can check some special cases: e.g. both x and y should be either odd or even numbers, i.e. we can check the least significant bit of x and y. However I wonder if I can improve the core algorithm itself.

3
  • 2
    Actually, I thought the obvious solution is to divide x by y then divide the result by y continually until you reach a number that is not divisible by y. If that number is 1, x is a power of y.
    – JeremyP
    Dec 13, 2010 at 13:19
  • Unfortunate that not a single user here noticed that every piece of code posted fails miserably for x = ±1
    – Nabb
    Dec 15, 2010 at 12:06
  • Nope, mine works for x = +1 (and a trivial abs fixes the negative numbers). Now y == 0, however. Dec 15, 2010 at 17:28

14 Answers 14

29

You'd do better to repeatedly divide y into x. The first time you get a non-zero remainder you know x is not an integer power of y.

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

This deals with your odd/even point on the first iteration.

14
  • 1
    Why is division better than multiplication ?
    – Michael
    Dec 13, 2010 at 13:11
  • 3
    @Michael: Suppose x is 123456789 and y is 2. Figure out how many iterations of multiplying by y you would have to do to get the answer and then figure out how many divisions you would have to do.
    – JeremyP
    Dec 13, 2010 at 13:21
  • 3
    It's also better than multiplication because it cannot overflow. And it could be possible that optimized code would skip your tries to detect the overflow.
    – ruslik
    Dec 13, 2010 at 19:15
  • 2
    Yes, but the average case is much better. If y isn't a factor of x (which will be true y-1 out of y times) you find out on first division. Dec 14, 2010 at 16:04
  • 3
    @Paul - 32-bit integer division would be about 10 times slower than multiplication (on x86 at least). You have to factor that into the analysis.
    – Axn
    Dec 14, 2010 at 21:06
22

It means logy(x) should be an integer. Don't need any loop. in O(1) time

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));
    }

}
5
  • 9
    You need to be careful of rounding issues with floating point numbers. Also how does isPower(-8, -2) fair?
    – JeremyP
    Dec 13, 2010 at 13:25
  • Yes, you are right. I thought integer is positive. Then, I should think it's abs version
    – user467871
    Dec 13, 2010 at 13:43
  • You should try isPower(1162261467, 3) x is greater one (int the question)
    – user467871
    Dec 13, 2010 at 13:46
  • 1
    +1 nice way, but, It's not O(1), Is O(log(x) + log(y)), Also using decimal is better to avoid rounding problems. Dec 17, 2010 at 15:14
  • I think your code fails for (17, -2). (You can correct it though).
    – azam
    Aug 13, 2016 at 22:04
7

This looks for the exponent in O(log N) steps:

#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);
}

Negative numbers are not handled by this code, but it can be done easyly with some conditional code when i = 1

2
  • Thanks for the idea of pre-calculating powers of y !
    – Michael
    Dec 13, 2010 at 17:19
  • This solution should be upvoted more. BTW, there is no way powers[99] will fit in an unsigned long if x > 1. For example, if x == 2 then powers 99 is roughly a one followed by a thousand billion billion billion zeros.
    – jonderry
    Dec 14, 2010 at 23:00
3

This looks to be pretty fast for positive numbers as it finds the lower and upper limits for desired power and then applies binary search.

#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);
}
3
    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");
    }
2

I would implement the function like so:

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

This shouldn't need check within a delta as is common with floating point comparisons, since we're checking whole numbers.

5
  • 1
    Now the question is how the "log" is implemented and why it is better than the loop.
    – Michael
    Dec 13, 2010 at 13:19
  • log(x) where x is a whole number is not a whole number. So, no you are not dealing with whole numbers. Also consider IsWholeNumberPower(-8, -2). The answer should be true.
    – JeremyP
    Dec 13, 2010 at 13:29
  • 1
    The log approach is better than the loop, IMO, because it makes clear your intention. So long as you know that the log of a number divided by the log of another number gives you the power the second number is raised to get the first, I can't think of a clearer method (I assume most people learn this at school, but I could be way off base). If you're looking for faster code, then I can't tell you, as I've not tested this in any language.
    – Matt Ellen
    Dec 13, 2010 at 13:29
  • @JeremyP: I did not meant that log(x) would give a whole number, I meant that you only want to check that log(x)/log(y) is a whole number, so checking that the answer is within a delta of floor the answer is not necessary. You are however correct, this won't work for negative numbers.
    – Matt Ellen
    Dec 13, 2010 at 13:33
  • @Matt Ellen: yes, but as log(x) is a transcendental number it will be rounded, similarly log(y), log(x)/log(y) may not come out as a whole number.
    – JeremyP
    Dec 13, 2010 at 13:47
2

On second thoughts, don't do this. It does not work for negative x and/or y. Note that all other log-based answers presented right now are also broken in exactly the same manner.

The following is a fast general solution (in 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;
}

Where pow() is an integer exponentiation function such as the following in Java:

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

(This works due to the following guarantee provided by Math.pow: "If both arguments are integers, then the result is exactly equal to the mathematical result of raising the first argument to the power of the second argument...")

The reason to go with logarithms instead of repeated division is performance: while log is slower than division, it is slower by a small fixed multiple. At the same time it does remove the need for a loop and therefore gives you a constant-time algorithm.

0
2

In cases where y is 2, there is a quick approach that avoids the need for a loop. This approach can be extended to cases where y is some larger power of 2.

If x is a power of 2, the binary representation of x has a single set bit. There is a fairly simple bit-fiddling algorithm for counting the bits in an integer in O(log n) time where n is the bit-width of an integer. Many processors also have specialised instructions that can handle this as a single operation, about as fast as (for example) an integer negation.

To extend the approach, though, first take a slightly different approach to checking for a single bit. First determine the position of the least significant bit. Again, there is a simple bit-fiddling algorithm, and many processors have fast specialised instructions.

If this bit is the only bit, then (1 << pos) == x. The advantage here is that if you're testing for a power of 4, you can test for pos % 2 == 0 (the single bit is at an even position). Testing for a power of any power of two, you can test for pos % (y >> 1) == 0.

In principle, you could do something similar for testing for powers of 3 and powers of powers of 3. The problem is that you'd need a machine that works in base 3, which is a tad unlikely. You can certainly test any value x to see if its representation in base y has a single non-zero digit, but you'd be doing more work that you're already doing. The above exploits the fact that computers work in binary.

Probably not worth doing in the real world, though.

3
  • the same idea can be applied to any base. It is not easy as shifting bits but it can be done using only basic arithmetic operations (+, *, /). See my own reply to the OP for an implementation in C.
    – salva
    Dec 13, 2010 at 16:03
  • 2
    There is a faster check for power-of-2. (x & (x-1)) == 0
    – Axn
    Dec 14, 2010 at 21:20
  • @Axn - I've seen that trick before, but I'm very prone to forgetting about it. Of course it's not faster than an intrinsic, but it's portable.
    – user180247
    Dec 18, 2010 at 4:45
2

Here is a Python version which puts together the ideas of @salva and @Axn and is modified to not generate any numbers greater than those given and uses only simple storage (read, "no lists") by repeatedly paring away at the number of interest:

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
2
# This version is robust with positive or negative integers.

def is_power_of(number, multiplier):
    """test if number is exactly multiplier^(some integer),
       inputs are positive or negative integers"""
    if number == 1: return True                  # Anything^0 == 1
    if multiplier == 0: return number in (0,1)   # 0^Positive == 0
                                                 # 0^0        == 1
                                                 # 0^Negative == illegal
    if multiplier == 1: return number == 1       # 1^0        == 1
                                                 # 1^Positive == 1
                                                 # 1^Negative == 1
    if multiplier == -1: return number in (-1,1) # -1^Odd     == -1
                                                 # -1^Even    == 1
    # now that multiplier >=2, accumulator will grow (might alternate sign)
    abs_number = abs(number)
    accumulator = multiplier
    while abs(accumulator) < abs_number:
        accumulator = accumulator * multiplier
    return accumulator == number
1

Previous answers are correct, I liked Paul's answer the best. It's Simple and clean. Here is the Java implementation of what he suggested:

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;
}
1

in the case the number is too large ... use log function to reduce time complexity:

import math
base = int(input("Enter the base number: "))
for i in range(base,int(input("Enter the end of range: "))+1):
    if(math.log(i) / math.log(base) % 1 == 0 ):
        print(i)
4
  • With base = 3 and i = 3**10, I get math.log(3**10) / math.log(3) % 1 == 0.9999999999999982 != 0, so this doesn't appear to work.
    – Stef
    Oct 3, 2023 at 13:26
  • Also note math.log accepts the base as a second parameter.
    – Stef
    Oct 3, 2023 at 13:33
  • For instance you could do instead: exponent = int(math.log(y, x) + 0.5); if y == x**exponent: print(f'{y} == {x}**{exponent}')
    – Stef
    Oct 3, 2023 at 13:33
  • Or use math.isclose instead of == to compare floats (although it might introduce false positives)
    – Stef
    Oct 3, 2023 at 13:36
0

I found this Solution

//Check for If A can be expressed as power of two integers

int isPower(int A)
{
        int i,a;
        double p;
        if(A==1)
                return 1;
        for(int a=1; a<=sqrt(A);++a )
        {
                p=log(A)/log(a);
                if(p-int(p)<0.000000001)
                        return 1;
        }
        return 0;
}

binarycoder.org

-1

If you have access to the largest power of y, that can be fitted inside the required datatype, this is a really slick way of solving this problem.

Lets say, for our case, y == 3. So, we would need to check if x is a power of 3.

Given that we need to check if an integer x is a power of 3, let us start thinking about this problem in terms of what information is already at hand.

1162261467 is the largest power of 3 that can fit into an Java int.
1162261467 = 3^19 + 0

The given x can be expressed as [(a power of 3) + (some n)]. I think it is fairly elementary to be able to prove that if n is 0(which happens iff x is a power of 3), 1162261467 % x = 0.

So, to check if a given integer x is a power of three, check if x > 0 && 1162261467 % x == 0.

Generalizing. To check if a given integer x is a power of a given integer y, check if x > 0 && Y % x == 0: Y is the largest power of y that can fit into an integer datatype.

The general idea is that if A is some power of Y, A can be expressed as B/Ya, where a is some integer and A < B. It follows the exact same principle for A > B. The A = B case is elementary.

3
  • There might be a couple of possible edge cases, but I think that can be ironed out. May 2, 2016 at 11:51
  • One edge case being the exponent of that high power not being prime.
    – greybeard
    May 2, 2016 at 19:01
  • Say x=8, y=4. Said largest power would be 2³⁰, an integer multiple of 8…
    – greybeard
    Dec 9, 2023 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.