Проверить, является ли число степенью другого числа

Опубликовано: 20 Января, 2022

Учитывая два положительных числа x и y, проверьте, является ли y степенью x или нет.
Примеры :

 Ввод: x = 10, y = 1
Выход: True
х ^ 0 = 1

Ввод: x = 10, y = 1000.
Выход: True
х ^ 3 = 1

Ввод: x = 10, y = 1001.
Выход: ложь

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

A simple solution is to repeatedly compute powers of x. If a power becomes equal to y, then y is a power, else not. 
 

C++

// C++ program to check if a number is power of
// another number
#include <bits/stdc++.h>
using namespace std;
 
/* Returns 1 if y is a power of x */
bool isPower(int x, long int y)
{
    // The only power of 1 is 1 itself
    if (x == 1)
        return (y == 1);
 
    // Repeatedly comput power of x
    long int pow = 1;
    while (pow < y)
        pow *= x;
 
    // Check if power of x becomes y
    return (pow == y);
}
 
/* Driver program to test above function */
int main()
{
    cout << isPower(10, 1) << endl;
    cout << isPower(1, 20) << endl;
    cout << isPower(2, 128) << endl;
    cout << isPower(2, 30) << endl;
    return 0;
}

Java

// Java program to check if a number is power of
// another number
public class Test {
    // driver method to test power method
    public static void main(String[] args)
    {
        // check the result for true/false and print.
        System.out.println(isPower(10, 1) ? 1 : 0);
        System.out.println(isPower(1, 20) ? 1 : 0);
        System.out.println(isPower(2, 128) ? 1 : 0);
        System.out.println(isPower(2, 30) ? 1 : 0);
    }
    /* Returns true if y is a power of x */
    public static boolean isPower(int x, int y)
    {
        // The only power of 1 is 1 itself
        if (x == 1)
            return (y == 1);
 
        // Repeatedly compute power of x
        int pow = 1;
        while (pow < y)
            pow = pow * x;
 
        // Check if power of x becomes y
        return (pow == y);
    }
}
 
// This code is contributed by Jyotsna.

Python3

# python program to check
# if a number is power of
# another number
 
# Returns true if y is a
# power of x
def isPower (x, y):
     
    # The only power of 1
    # is 1 itself
    if (x == 1):
        return (y == 1)
         
    # Repeatedly compute
    # power of x
    pow = 1
    while (pow < y):
        pow = pow * x
 
    # Check if power of x
    # becomes y
    return (pow == y)
     
     
# Driver Code
# check the result for
# true/false and print.
if(isPower(10, 1)):
    print(1)
else:
    print(0)
 
if(isPower(1, 20)):
    print(1)
else:
    print(0)
if(isPower(2, 128)):
    print(1)
else:
    print(0)
if(isPower(2, 30)):
    print(1)
else:
    print(0)
     
# This code is contributed
# by Sam007.

C#

// C# program to check if a number
// is power of another number
using System;
 
class GFG
{
     
    // Returns true if y is a power of x
    public static bool isPower (int x, int y)
    {
        // The only power of 1 is 1 itself
        if (x == 1)
        return (y == 1);
 
        // Repeatedly compute power of x
        int pow = 1;
        while (pow < y)
        pow = pow * x;
 
        // Check if power of x becomes y
        return (pow == y);
    }
     
    // Driver Code
    public static void Main ()
    {
        //check the result for true/false and print.
        Console.WriteLine(isPower(10, 1) ? 1 : 0);
        Console.WriteLine(isPower(1, 20) ? 1 : 0);
        Console.WriteLine(isPower(2, 128) ? 1 : 0);
        Console.WriteLine(isPower(2, 30) ? 1 : 0);
    }
     
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP program to check if a
// number is power of another number
 
/* Returns 1 if y is a power of x */
function isPower($x, $y)
{
    // The only power of 1 is 1 itself
    if ($x == 1)
        return ($y == 1 ? 1 : 0);
 
    // Repeatedly comput power of x
    $pow = 1;
    while ($pow < $y)
        $pow *= $x;
 
    // Check if power of x becomes y
    return ($pow == $y ? 1 : 0);
}
 
// Driver Code
echo isPower(10, 1) . " ";
echo isPower(1, 20) . " ";
echo isPower(2, 128) . " ";
echo isPower(2, 30) . " ";
 
// This code is contributed by mits
?>

Javascript

<script>
 
// JavaScript program to check if a number
// is power of another number
   
/* Returns true if y is a power of x */
    function isPower(x, y)
    {
        // The only power of 1 is 1 itself
        if (x == 1)
            return (y == 1);
   
        // Repeatedly compute power of x
        let pow = 1;
        while (pow < y)
            pow = pow * x;
   
        // Check if power of x becomes y
        return (pow == y);
    }
 
 
// Driver Code
 
        //check the result for true/false and print.
        document.write((isPower(10, 1) ? 1 : 0) + "<br/>");
           document.write((isPower(1, 20) ? 1 : 0) + "<br/>");
        document.write((isPower(2, 128) ? 1 : 0) + "<br/>");
        document.write((isPower(2, 30) ? 1 : 0) + "<br/>");
 
</script>

Выход:

 1
0
1
0

Временная сложность вышеуказанного решения составляет O (Log x y)
Оптимизация:
Мы можем оптимизировать вышеуказанное решение для работы в O (Log Log y). Идея состоит в том, чтобы возвести мощность в квадрат вместо умножения ее на x, то есть сравнить y с x ^ 2, x ^ 4, x ^ 8 и т. Д. Если x становится равным y, верните true. Если x становится больше, чем y, мы выполняем двоичный поиск мощности x между предыдущей мощностью и текущей мощностью, то есть между x ^ i и x ^ (i / 2).
Ниже приведен подробный шаг.

1) Initialize pow = x, i = 1
2) while (pow < y)
   {
      pow = pow*pow 
      i *= 2
   }    
3) If pow == y
     return true;
4) Else construct an array of powers
   from x^i to x^(i/2)
5) Binary Search for y in array constructed
   in step 4. If not found, return false. 
   Else return true.

Alternate Solution : 
The idea is to take log of y in base x. If it turns out to be an integer, we return true. Else false. 
 

C++

// CPP program to check given number number y
// is power of x
#include <iostream>
#include <math.h>
using namespace std;
 
bool isPower(int x, int y)
{
    // logarithm function to calculate value
    int res1 = log(y) / log(x);
    double res2 = log(y) / log(x); // Note : this is double
 
    // compare to the result1 or result2 both are equal
    return (res1 == res2);
}
 
// Driven program
int main()
{
    cout << isPower(27, 729) << endl;
    return 0;
}

Java

// Java program to check given
// number y is power of x
 
class GFG
{
    static boolean isPower(int x,
                           int y)
    {
        // logarithm function to
        // calculate value
        int res1 = (int)Math.log(y) /
                   (int)Math.log(x);
                    
         // Note : this is double         
        double res2 = Math.log(y) /
                      Math.log(x);
     
        // compare to the result1 or
        // result2 both are equal
        return (res1 == res2);
    }
     
    // Driver Code
    public static void main(String args[])
    {
        if(isPower(27, 729))
            System.out.println("1");
        else
            System.out.println("0");
    }
}
 
// This code is contributed by Sam007

Python3

# Python3 program to check
# given number number y
import math
def isPower(x, y):
    # logarithm function to
    # calculate value
    res1 = math.log(y) // math.log(x);
     
    # Note : this is double
    res2 = math.log(y) / math.log(x);
 
    # compare to the result1 or
    # result2 both are equal
    return 1 if(res1 == res2) else 0;
 
# Driver Code
if __name__=="__main__":
    print(isPower(27, 729));
 
# This code is contributed by mits
# Improved by hsagarthegr8

C#

// C# program to check given
// number y is power of x
using System;
class GFG
{
static bool isPower(int x, int y)
{
    // logarithm function to
    // calculate value
    int res1 = (int)Math.Log(y) /
               (int)Math.Log(x);
                 
    // Note : this is double        
    double res2 = Math.Log(y) /
                  Math.Log(x);
 
    // compare to the result1 or
    // result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
static void Main()
{
    if(isPower(27, 729))
        Console.WriteLine("1");
    else
        Console.WriteLine("0");
}
}
 
// This code is contributed by mits

PHP

<?php
// PHP program to check
// given number number y
function isPower($x, $y)
{
    // logarithm function to
    // calculate value
    $res1 = log($y) / log($x);
     
    // Note : this is double
    $res2 = log($y) / log($x);
 
    // compare to the result1 or
    // result2 both are equal
    return ($res1 == $res2);
}
 
// Driver Code
echo isPower(27, 729) ;
 
// This code is contributed by Sam007
?>

Javascript

<script>
 
// javascript program to check given
// number y is power of x{
function isPower(x, y)
{
 
    // logarithm function to
    // calculate value
    var res1 = parseInt(Math.log(y)) /
               parseInt(Math.log(x));
                
     // Note : this is var         
    var res2 = Math.log(y) /
                  Math.log(x);
 
    // compare to the result1 or
    // result2 both are equal
    return (res1 == res2);
}
 
// Driver Code
if(isPower(27, 729))
    document.write("1");
else
    document.write("0");
 
// This code is contributed by Princi Singh
</script>

Выход :

 1

Спасибо Gyayak Jain за предложение этого решения.
Автор статьи - Маниш Гупта . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ