Рубрики

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

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

Примеры :

Input:  x = 10, y = 1
Output: True
x^0 = 1

Input:  x = 10, y = 1000
Output: True
x^3 = 1

Input:  x = 10, y = 1001
Output: False

Простым решением является многократное вычисление степеней х. Если сила становится равной y, то y — это сила, иначе нет.

C ++

// C ++ программа для проверки, является ли число степенью
// другой номер
#include <bits/stdc++.h>

using namespace std;

  
/ * Возвращает 1, если у степень х * /

bool isPower(int x, long int y)

{

    // Единственная степень 1 - это сама 1

    if (x == 1)

        return (y == 1);

  

    // Многократно вычисляем мощность х

    long int pow = 1;

    while (pow < y)

        pow *= x;

  

    // Проверяем, становится ли сила х у

    return (pow == y);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

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-программа для проверки, является ли число степенью
// другой номер

public class Test {

    // метод драйвера для проверки метода питания

    public static void main(String[] args)

    {

        // проверяем результат на true / false и печатаем.

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

    }

    / * Возвращает истину, если у степень х * /

    public static boolean isPower(int x, int y)

    {

        // Единственная степень 1 - это сама 1

        if (x == 1)

            return (y == 1);

  

        // Многократно вычисляем мощность х

        int pow = 1;

        while (pow < y)

            pow = pow * x;

  

        // Проверяем, становится ли сила х у

        return (pow == y);

    }

}

  
// Этот код предоставлен Jyotsna.

python3

# Python программа для проверки
# если число является степенью
# другой номер

  
# Возвращает true, если y является
# сила х

def isPower (x, y):

      

    # Единственная сила 1

    # - это сам 1

    if (x == 1):

        return (y == 1)

          

    # Неоднократно вычислять

    # сила х

    pow = 1

    while (pow < y):

        pow = pow * x

  

    # Проверьте, если сила х

    # становится у

    return (pow == y)

      

      
Код водителя
# проверить результат для
# true / false и распечатать.

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)

      
# Этот код добавлен
# Sam007.

C #

// C # программа для проверки, если число
// это сила другого числа

using System;

  

class GFG

{

      

    // Возвращает истину, если у степень х

    public static bool isPower (int x, int y)

    {

        // Единственная степень 1 - это сама 1

        if (x == 1)

        return (y == 1);

  

        // Многократно вычисляем мощность х

        int pow = 1;

        while (pow < y)

        pow = pow * x;

  

        // Проверяем, становится ли сила х у

        return (pow == y);

    }

      

    // Код драйвера

    public static void Main ()

    {

        // проверяем результат на true / false и печатаем.

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

    }

      
}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для проверки
// число - это сила другого числа

  
/ * Возвращает 1, если у степень х * /

function isPower($x, $y)

{

    // Единственная степень 1 - это сама 1

    if ($x == 1)

        return ($y == 1 ? 1 : 0);

  

    // Многократно вычисляем мощность х

    $pow = 1;

    while ($pow < $y)

        $pow *= $x;

  

    // Проверяем, становится ли сила х у

    return ($pow == $y ? 1 : 0);

}

  
// Код драйвера

echo isPower(10, 1) . "\n";

echo isPower(1, 20) . "\n";

echo isPower(2, 128) . "\n";

echo isPower(2, 30) . "\n";

  
// Этот код предоставлен mits
?>

Выход:

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.

Альтернативное решение:
Идея состоит в том, чтобы взять журнал у в базе х. Если это целое число, мы возвращаем true. Остальное ложно.

C ++

// Программа CPP для проверки заданного числа номер y
// это степень х
#include <iostream>
#include <math.h>

using namespace std;

  

bool isPower(int x, int y)

{

    // функция логарифма для вычисления значения

    int res1 = log(y) / log(x);

    double res2 = log(y) / log(x); // Примечание: это двойное

  

    // сравниваем с result1 или result2 оба равны

    return (res1 == res2);

}

  
// Управляемая программа

int main()

{

    cout << isPower(27, 729) << endl;

    return 0;

}

Джава

// Java-программа для проверки заданного
// число у - степень х

  

class GFG 

{

    static boolean isPower(int x, 

                           int y)

    {

        // функция логарифма для

        // вычисляем значение

        int res1 = (int)Math.log(y) / 

                   (int)Math.log(x);

                     

         // Примечание: это двойное

        double res2 = Math.log(y) / 

                      Math.log(x); 

      

        // сравнить с результатом1 или

        // result2 оба равны

        return (res1 == res2);

    }

      

    // Код драйвера

    public static void main(String args[]) 

    {

        if(isPower(27, 729))

            System.out.println("1");

        else

            System.out.println("0");

    }

}

  
// Этот код предоставлен Sam007

python3

# Python3 программа для проверки
# заданный номер номер у

import math

def isPower(x, y):

    # функция логарифма для

    # вычислить значение

    res1 = math.log(y) / math.log(x);

      

    # Примечание: это двойной

    res2 = math.log(y) / math.log(x); 

  

    # сравнить с результатом1 или

    # result2 оба равны

    return 1 if(res1 == res2) else 0;

  
Код водителя

if __name__=='__main__':

    print(isPower(27, 729));

  
# Этот код предоставлен mits

C #

// C # программа для проверки заданного
// число у - степень х

using System;

class GFG 

{

static bool isPower(int x, int y)

{

    // функция логарифма для

    // вычисляем значение

    int res1 = (int)Math.Log(y) / 

               (int)Math.Log(x);

                  

    // Примечание: это двойное

    double res2 = Math.Log(y) / 

                  Math.Log(x); 

  

    // сравнить с результатом1 или

    // result2 оба равны

    return (res1 == res2);

}

  
// Код драйвера

static void Main() 

{

    if(isPower(27, 729))

        Console.WriteLine("1");

    else

        Console.WriteLine("0");

}
}

  
// Этот код предоставлен mits

PHP

<?php
// PHP программа для проверки
// заданный номер номер у

function isPower($x, $y)

{

    // функция логарифма для

    // вычисляем значение

    $res1 = log($y) / log($x);

      

    // Примечание: это двойное

    $res2 = log($y) / log($x); 

  

    // сравнить с результатом1 или

    // result2 оба равны

    return ($res1 == $res2);

}

  
// Код драйвера

echo isPower(27, 729) ;

  
// Этот код предоставлен Sam007
?>


Выход :

1

Спасибо Gyayak Jain за предложение этого решения.

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

Рекомендуемые посты:

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

0.00 (0%) 0 votes