trjhtr

Challenge:

Given a positive integer which fits in a $32$ bit signed integer,
find if it can be expressed as $A^P$ where $P > 1$ and $A > 0$.
A and P both should be integers.

Example

Input : 4

Output : True

as $2^2 = 4$.

My approach:

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; 
 

 

I have the following questions with regards to the above code:

1. Is there any better method to solve this question?




2. How can I further optimise the time and space complexity of the solution?

Accuracy

Floating-point approximations are not an acceptable substitute for integer arithmetic! Otherwise, you end up with mistakes, like Homer's bogus counterexample of Fermat's Last Theorem.

How does that apply to your code? Consider isPower(2147483647). Your code yields 1, because it thinks that 46341²Ã‚ â‰ˆÂ 2147483647. In fact, 46341²Ã‚ = 2147488281, and the correct answer is "false", since 2147483647 is prime.

Filtering a number through a double → String → double round-trip conversion is especially egregious.

Naming

Try to choose variable names that are consistent with the nomenclature in the challenge. Your variable is really P; your i corresponds to A; your A should be named something else altogether — perhaps n.

Suggested solution

Count the number of times each prime factor of n occurs. You need to be able to segregate those factors into equal groups, with no lone factors left over.

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;
 

1. The challenge defines the output of your function to be true or false. Java has the boolean primitive to model exactly that. Your method should return a boolean not an int that "means" true when it's not 0 (as would be the case for C).




2. It's generally accepted best practice in java to define each variable (and member) on its own line. exp and base should be declared on separate lines.




3. It's easier on your brain to keep track of things, if you're using them directly after you introduced them. That is generally referred to as "Declaring variables as close as possible to their usage".




4. The vast majority of java conventions states that binary and ternary operators should have spaces around the operators. In your code that applies to +=, % and sometimes ==. Generally your formatting seems to try matching some standard, but isn't quite consistent, as evidenced by / having spacing when you calculate variable, but not when inside a a for-loop's head...
   
   Above all you should strive to be consistent with formatting code. That makes it easier to read.




5. Most Java conventions prefer opening braces to be on the same line as the block opening statement. That implies the same bracing style as you use for the method definition to extend to if, else and for statements.
   
   In addition to that I highly recommend placing braces wherever possible.




6. Lastly: the for-loops in if (A % 2 == 0) and else only differ by their initial value. Aside from that they are the same. Why did you opt for using a step-size of two with starts differing by one when you could've just as well iterated with a step-size of 1?

For a given number N, you do a loop over the potential base numbers A, and calculate the exponent P, checking whether it's integer. This way, you have to loop over a lot of numbers.

If you do it the other way round, with a loop over the potential exponents P, calculating the matching base A and checking that for an integer value, you only have to iterate from P=2 to P=30.

I didn't check if your code works - I have my doubts, especially with the "check for integer" part.

A few comments on your coding style:

Your method isPower() is meant to check if the given number can be represented as a power A^P. Instead of an int you should return a boolean (true or false instead of 1 or 0).

The naming of classes, methods, fields, variables and so on is crucial for the readability of code. They should reflect the thing they represent. So, isPower is a good name for a method that checks whether the number is a power. But names like variable don't help. Names like exp and base are good choices, but you only declare them and don't use them (any decent IDE will flag them as unused). One-letter names should be avoided as much as possible (with the exception of loop variables like i, j, or k).

There are naming conventions in Java, especially variables should always begin with a lowercase letter. Long-term Java developers will automatically understand anything that begins with uppercase as a class name, and have a hard time if in your code, the conventions don't apply.

Your indentation and placement of braces is unique. Following the usual style makes it easier to read your code and doesn't waste so much space (even the simple class presented here has lines too wide to fit into the space on this site).

Code like

 if( A == 1)
 return 1;

not surrounding the dependent statement with braces, is a maintenance risk. Imagine that later someone wants to add another statement here:

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

That looks fine at a first glance, but effectively it's:

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

Not what you want, isn't it? So, I recommend to always use braces.

Write Javadoc comments at least for all public classes and methods.

After renaming, commenting and reformatting your code (but keeping your algorithm), we'd get:

/**
 * 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</code> can be represented as <code>A^P</code>
 * with A and P being integers, and P greater that 1.
 * @param power the number under test
 * @return true if <code>power</code> can be represented as <code>A^P</code>
 */
 public boolean isPower(int power) 
 if (power == 1) 
 return true;
 

 if (power % 2 == 0) 
 for (int base = 2; base < power; base += 2) 
 double exp = Math.log(power) / Math.log(base);
 double formattedExp = Double.parseDouble(String.format("%.6f", exp));

 if ((formattedExp == Math.floor(formattedExp)) && !Double.isInfinite(formattedExp)) 
 return true;
 
 
 return false;

 else 
 for (int base = 3; base < power / 2; base += 2) 
 double exp = Math.log(power) / Math.log(base);
 double formattedExp = Double.parseDouble(String.format("%.6f", exp));

 if ((formattedExp == Math.floor(formattedExp)) && !Double.isInfinite(formattedExp)) 
 return true;
 
 
 return false;
 
 

There are some valid points regarding coding style and floating point arithmetic, but I want to focus on improving the time complexity of the solution. From my experiments, it seems that simpler is better. Simply looping over bases and exponents yields a result which is >20x faster than the previous answers posted here.

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;
 

Disclosure: I copied the pow2 function from here.

Explanation: since the input was a positive integer, we first create special cases for n<4. For every other value of n, test every value of a which is a suitable candidate. There's no need to check beyond sqrt(n), because the lowest exponent is p=2.

With some math, you can figure out that given the base a, the exponent p should be approximately log(n)/log(a). Since n fits within a signed 32-bit integer, we know that p<32.

Then we simply compute a^p and check if it is equal to n. Simple as that. This code outputs identical results for all values of n less than 100000 (that's how far I tested) compared to previous solutions in this thread.

Possible future improvements: remove all floating point arithmetic and instead use bit-shift operations to approximate the logarithm, and do a special case to see if n only has one bit set (e.g. 0b00100000), which implies that it is a power of 2.

EDIT: additional speedup

After some research, I concluded that reversing the search order would make the function faster. Since we know that 1<p<lg(n)+1, we can try all those values, and perform a binary search for the value of 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;

Some included benchmarks:

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

From this benchmark we can see that the new algorithm is much faster for large values of n, being almost 100 times faster in the last benchmark.