CODEWITHSUNDEEP
phpmathexponential
user3445122
user3445122

Reputation:

For a given integer Z, check if Z can be written as P^Q where Q and P are positive integers

Here is what I have tried but it is giving me wrong output. Can anyone point out what is the mistake?

function superPower($n) {
    $response = false;
    $n = abs($n);
    if ($n < 2) { 
       $response = true;
    }
    for ($i=2;$i<$n;$i++) {    
        for ($j=2;$j<$n;$j++) {
            if (pow($i,$j) == $n) {
                $response = true;
            }
        }
    }  

    return $response;   
}

For example if I give it number 25, it gives 1 as output. //Correct But if I give it 26 it still gives me 1 which is wrong.

Upvotes: 3

Views: 1706

Answers (2)

UrsaDK
UrsaDK

Reputation: 865

The maths on the accepted answer is absolutely brilliant, however there are a couple of issues with the solution:

  • the function erroneously returns true for all of the following inputs: monkey, -3 and 0. (Technically 0 is unsigned, so there is no way of getting it by taking a positive integer to the power of another positive integer. The same goes for any negative input.)

  • the function compares floating numbers with integers (floor() and ceil() return float), which should be avoided like the plague. To see why, try running php -r '$n = (-(4.42-5))/0.29; echo "n == {$n}\n".($n == 2 ? "OK" : "Surprise")."\n";'

The following solution improves on the idea by fixing all of the above issues:

function superPower($value)
{
    // Fail if supplied value is not numeric
    if (!is_numeric($value)) {
        // throw new InvalidArgumentException("Value is not numeric: $value");
        return false;
    }

    // Normalise numeric input
    $number = abs($value);

    // Fail if supplied number is not an integer
    if (!is_int($number)) {
        // throw new InvalidArgumentException("Number is not an integer: $number");
        return false;
    }

    // Exit early if possible
    if ($number == 1) {
        // 1 to the power of any positive integer is one
        return true;
    } elseif ($number < 1) {
        // X to the power of Y is never less then 1, if X & Y are greater then 0
        return false;
    }

    // Determine the highest logarithm base and work backwards from it
    for ($base = (int) sqrt($number); $base > 1; $base--) {
        $coefficient = log($number)/log($base);

        // Check that the result of division is a whole number
        if (ctype_digit((string) $coefficient)) {
            return true;
        }
    }

    return false;
}

Upvotes: 2

Niet the Dark Absol
Niet the Dark Absol

Reputation: 324650

By using superPower, you are essentially trying to put a certain defence to the power of an attack to see if it holds up. This can be done much more effectively than through the brute-force method you have now.

function superPower( $hp) { // Niet used Superpower!
    if( $hp <= 1) return true;

    for( $def = floor(sqrt($hp)); $def > 1; $def--) { // Niet's Defence fell
        for( $atk = ceil(log($hp)/log($def)); $atk > 1; $atk--) { // Niet's Attack fell
            if( pow($def,$atk) == $hp) return true;
            break;
            // you don't need the $atk loop, but I wanted to make a Pokémon joke. Sorry.
        }
        // in fact, all you really need here is:
        // $atk = log($hp)/log($def);
        // if( $atk-floor($atk) == 0) return true;
    }
    return false;
}

Upvotes: 7

Related Questions