Power of two integers Challenge:


  Given a positive integer which fits in a \$32\$ bit signed integer,
  find if it can be expressed as \$A^P\$ where \$P &gt; 1\$ and \$A &gt; 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 &lt; A; i+= 2 )
                  {
                        double variable = Math.log(A) / Math.log(i);
                        double formatted = Double.parseDouble(String.format( "%.6f", variable));

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

        else
            {
                for( int i = 3; i &lt; 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)) &amp;&amp; !Double.isInfinite(formatted))
                           return 1;
                  }
                return 0;    
            }        

    }
}


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


Is there any better method to solve this question?
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 463412 ≈ 2147483647.  In fact, 463412 = 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 -&gt; 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 &gt; 0) {
                exponents.add(e);
            }
        } while (f &lt; 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 &gt; 1;
    }
}