Dado un entero positivo, escribe una función para encontrar si es una potencia de tres o no.
Ejemplos:
Input : 3 Output :Yes Input :6 Output :No
Enfoque recursivo:
Compruebe si el número es divisible por 3, si es así, siga comprobando lo mismo para el número/3 recursivamente. Si el número se puede reducir a 1, entonces el número es divisible por 3, de lo contrario no.
C++
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool isPower_of_Three(ll n)
{
if (n <= 0)
return false;
if (n % 3 == 0)
return isPower_of_Three(n / 3);
if (n == 1)
return true;
return false;
}
int main()
{
ll num1;
num1 = 243;
if (isPower_of_Three(num1))
cout << "Yes" << endl;
else
cout << "No" << endl;
ll num2 = 6;
if (isPower_of_Three(num2))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
C
#include <stdbool.h>
#include <stdio.h>
#define ll long long
bool isPower_of_Three(ll n)
{
if (n <= 0)
return false;
if (n % 3 == 0)
return isPower_of_Three(n / 3);
if (n == 1)
return true;
return false;
}
int main()
{
ll num1;
num1 = 243;
if (isPower_of_Three(num1))
printf("Yes\n");
else
printf("No\n");
ll num2 = 6;
if (isPower_of_Three(num2))
printf("Yes\n");
else
printf("No\n");
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
Java
import java.util.*;
class GFG{
static boolean isPower_of_Three(long n)
{
if (n <= 0)
return false;
if (n % 3 == 0)
return isPower_of_Three(n / 3);
if (n == 1)
return true;
return false;
}
// Driver code
public static void main(String[] args)
{
long num1 = 243;
if (isPower_of_Three(num1))
System.out.print("Yes" +"\n");
else
System.out.print("No" +"\n");
long num2 = 6;
if (isPower_of_Three(num2))
System.out.print("Yes" +"\n");
else
System.out.print("No" +"\n");
}
}
// This code is contributed by umadevi9616
Python3
def isPower_of_Three(n):
if (n <= 0):
return False
if (n % 3 == 0):
return isPower_of_Three(n // 3)
if (n == 1):
return True
return False
# Driver code
num1 = 243
if (isPower_of_Three(num1)):
print("Yes")
else:
print("No")
num2 = 6
if (isPower_of_Three(num2)):
print("Yes")
else:
print("No")
# This code is contributed by shivanisinghss2110
C#
using System;
class GFG{
static Boolean isPower_of_Three(long n)
{
if (n <= 0)
return false;
if (n % 3 == 0)
return isPower_of_Three(n / 3);
if (n == 1)
return true;
return false;
}
// Driver code
public static void Main(String[] args)
{
long num1 = 243;
if (isPower_of_Three(num1))
Console.Write("Yes" +"\n");
else
Console.Write("No" +"\n");
long num2 = 6;
if (isPower_of_Three(num2))
Console.Write("Yes" +"\n");
else
Console.Write("No" +"\n");
}
}
// this code is contributed by shivanisinghss2110
Javascript
<script>
function isPower_of_Three(n)
{
if (n <= 0)
return false;
if (n % 3 == 0)
return isPower_of_Three(n / 3);
if (n == 1)
return true;
return false;
}
let num1 = 243;
if (isPower_of_Three(num1))
document.write("Yes");
else
document.write("No");
let num2 = 6;
if (isPower_of_Three(num2))
document.write("Yes");
else
document.write("</br>No");
//This code is contributed by vaibhavrabadiyaa3.
</script>
PHP
<?php
function isPower_of_Three($n)
{
if ($n <= 0)
return false;
if ($n % 3 == 0)
return isPower_of_Three($n / 3);
if ($n == 1)
return true;
return false;
}
$num1 = 243;
if (isPower_of_Three($num1))
echo("Yes");
else
echo("No");
echo("\n");
$num2 = 6;
if (isPower_of_Three($num2))
echo("Yes");
else
echo("No");
// This code is contributed by laxmigangarajula03
?>
Yes No
Complejidad de tiempo: O(log 3 n), donde n representa el entero dado.
Espacio Auxiliar: O(log 3 n).
Enfoque:
La lógica es muy simple. Cualquier número entero que no sea una potencia de 3 que divide el valor de la potencia más alta de 3 que el entero puede contener 3 ^ 19 = 1162261467 (suponiendo que los números enteros se almacenan usando 32 bits) dará un recordatorio distinto de cero.
C++
// C++ program to check if a number is power
// of 3 or not.
#include <iostream>
using namespace std;
// Returns true if n is power of 3, else false
bool check(int n)
{
if (n <= 0)
return false;
/* The maximum power of 3 value that
integer can hold is 1162261467 ( 3^19 ) .*/
return 1162261467 % n == 0;
}
// Driver code
int main()
{
int n = 9;
if (check(n))
cout <<"Yes";
else
cout <<"No";
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C++ program to check if a number is power
// of 3 or not.
#include <stdio.h>
#include <stdbool.h>
// Returns true if n is power of 3, else false
bool check(int n)
{
if (n <= 0)
return false;
/* The maximum power of 3 value that
integer can hold is 1162261467 ( 3^19 ) .*/
return 1162261467 % n == 0;
}
// Driver code
int main()
{
int n = 9;
if (check(n))
printf("Yes");
else
printf("No");
return 0;
}
Java
// Java program to check if a number is power
// of 3 or not.
public class Power_3 {
// Returns true if n is power of 3, else false
static boolean check(int n)
{
/* To prevent
java.lang.ArithmeticException: / by zero and
negative n */
if (n <= 0)
return false;
/* The maximum power of 3 value that
integer can hold is 1162261467 ( 3^19 ) .*/
return 1162261467 % n == 0;
}
// Driver code
public static void main(String args[])
{
int n = 9;
if (check(n))
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Sumit Ghosh
Python
# Python program to check if a number is power
# of 3 or not.
# Returns true if n is power of 3, else false
def check(n):
""" The maximum power of 3 value that
integer can hold is 1162261467 ( 3^19 ) ."""
return 1162261467 % n == 0
# Driver code
n = 9
if (check(n)):
print ("Yes")
else:
print ("No")
# This code is contributed by Sachin Bisht
C#
// C# program to check if a number
// is power of 3 or not.
using System;
public class GFG {
// Returns true if n is power
// of 3, else false
static bool check(int n)
{
if (n <= 0)
return false;
/* The maximum power of 3
value that integer can hold
is 1162261467 ( 3^19 ) .*/
return 1162261467 % n == 0;
}
// Driver code
public static void Main()
{
int n = 9;
if (check(n))
Console.Write("Yes");
else
Console.Write("No");
}
}
// This code is contributed by
// nitin mittal.
PHP
<?php
// PHP program to check if a
// number is power of 3 or not.
// Returns true if n is
// power of 3, else false
function check($n)
{
/* The maximum power of 3 value that
integer can hold is 1162261467
( 3^19 ) . */
return 1162261467 % $n == 0;
}
// Driver code
$n = 9;
if (check($n))
echo("Yes");
else
echo("No");
// This code is contributed by nitin mittal
?>
Javascript
<script>
// Javascript program to check if a
// number is power of 3 or not.
// Returns true if n is
// power of 3, else false
function check(n)
{
/* The maximum power of 3 value that
integer can hold is 1162261467
( 3^19 ) . */
return 1162261467 % n == 0;
}
// Driver code
let n = 9;
if (check(n))
document.write("Yes");
else
document.write("No");
// This code is contributed by nitin _saurabh_jaiswal
</script>
Yes
Complejidad de tiempo : O(1)
Espacio auxiliar: O(1)
Este artículo es una contribución de Jebasingh y Riyazath .
Acercarse:
Este enfoque se basa en las siguientes observaciones simples.
Observación 1 : si hay una potencia de tres números, definitivamente terminará en 3, 9, 7 o 1.
Observación 2 : Si un número termina con uno de estos 4 dígitos, solo tenemos que verificar las potencias de tres que garantizarían un número que termina con ese último dígito. Por ejemplo, si un número determinado termina en 1, debe ser un 4, un 8 o un 12 y así sucesivamente en potencia de tres, si es que lo es.
Ahora que somos claros con las observaciones, echemos un vistazo al algoritmo.
Algoritmo:
Paso 1: si el número dado, n, no termina en 3, 9, 7 o 1, significa que el número no es una potencia de tres, por lo tanto, devuelve FALSO.
Paso 2: si no, creamos un mapa con 4 entradas para mantener el mapeo entre las potencias de tres (1,2,3,4) y los últimos dígitos del número (3,9,7,1).
Paso 3: extrae el último dígito de un número dado y busca su potencia correspondiente en el mapa.
Paso 4: si esta potencia cuando se eleva a tres es igual al número n, devuelve VERDADERO.
Paso 5: Si esta potencia elevada a tres es menor que el número n, incremente la potencia directamente en 4 y repita el paso 4 hasta que la potencia elevada a tres sea mayor que n.
Paso 6: Si la potencia elevada a tres se vuelve mayor que el número dado, devuelve FALSO.
C++
#include <bits/stdc++.h>
using namespace std;
bool isPowerOfThree(int n)
{
if (n == 1)
return true;
int lastDigit = n % 10;
map<int, int> map;
map[3] = 1;
map[9] = 2;
map[7] = 3;
map[1] = 4;
if (!map[lastDigit])
return false;
int power = map[lastDigit];
double powerOfThree = pow(3, power);
while (powerOfThree <= n) {
if (powerOfThree == n)
return true;
power = power + 4;
powerOfThree = pow(3, power);
}
return false;
}
int main()
{
int n = 81;
cout << (isPowerOfThree(n) ? "true" : "false") << endl;
n = 91;
cout << (isPowerOfThree(n) ? "true" : "false") << endl;
return 0;
}
// This code is contributed by umadevi9616
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
public static boolean isPowerOfThree(int n)
{
if (n == 1)
return true;
int lastDigit = n % 10;
Map<Integer, Integer> map = new HashMap<>();
map.put(3, 1);
map.put(9, 2);
map.put(7, 3);
map.put(1, 4);
if (map.get(lastDigit) == null)
return false;
int power = map.get(lastDigit);
double powerOfThree = Math.pow(3, power);
while (powerOfThree <= n) {
if (powerOfThree == n)
return true;
power = power + 4;
powerOfThree = Math.pow(3, power);
}
return false;
}
public static void main(String[] args)
{
int n = 81;
System.out.println(isPowerOfThree(n));
n = 91;
System.out.println(isPowerOfThree(n));
}
}
Python3
'''package whatever #do not write package name here ''' def isPowerOfThree(n): if (n == 1): return True; lastDigit = n % 10; map =[0] * 1000; map[3] = 1; map[9] = 2; map[7] = 3; map[1] = 4; if (map[lastDigit] == None): return False; power = map[lastDigit]; powerOfThree = pow(3, power); while (powerOfThree <= n): if (powerOfThree == n): return True; power = power + 4; powerOfThree = pow(3, power); return False; if __name__ == '__main__': n = 81; print(isPowerOfThree(n)); n = 91; print(isPowerOfThree(n)); # This code contributed by umadevi9616
C#
/*package whatever //do not write package name here */
using System;
using System.Collections.Generic;
public class GFG {
public static bool isPowerOfThree(int n)
{
if (n == 1)
return true;
int lastDigit = n % 10;
Dictionary<int, int> map = new Dictionary<int,int>();
map.Add(3, 1);
map.Add(9, 2);
map.Add(7, 3);
map.Add(1, 4);
if (!map.ContainsValue(lastDigit))
return false;
int power = map[lastDigit];
double powerOfThree = Math.Pow(3, power);
while (powerOfThree <= n) {
if (powerOfThree == n)
return true;
power = power + 4;
powerOfThree = Math.Pow(3, power);
}
return false;
}
public static void Main(String[] args)
{
int n = 81;
Console.WriteLine(isPowerOfThree(n));
n = 91;
Console.WriteLine(isPowerOfThree(n));
}
}
// This code is contributed by umadevi9616
Javascript
<script>
/*package whatever //do not write package name here */
function isPowerOfThree(n) {
if (n == 1)
return true;
var lastDigit = n % 10;
var map = new Map();
map.set(3, 1);
map.set(9, 2);
map.set(7, 3);
map.set(1, 4);
if (map.get(lastDigit) == null)
return false;
var power = map.get(lastDigit);
var powerOfThree = Math.pow(3, power);
while (powerOfThree <= n) {
if (powerOfThree == n)
return true;
power = power + 4;
powerOfThree = Math.pow(3, power);
}
return false;
}
// Driver code
var n = 81;
document.write(isPowerOfThree(n)+"<br/>");
n = 91;
document.write(isPowerOfThree(n));
// This code is contributed by umadevi9616
</script>
true false
Análisis:
Complejidad del tiempo de ejecución:
O(1): dado que el número dado es un número entero, puede ser como máximo 2147483647 (32 bits) y la potencia más alta de tres que es menor o igual a este número es 3^19 = 1162261467. Y dado que incrementamos el potencia por 4, tendremos un bucle ejecutándose como máximo 5 veces, por lo tanto, O (1).
Complejidad espacial:
O(1): Dado que solo tenemos 4 entradas en un Mapa, no importa cuán grande sea el número que se nos dé.
Este enfoque es aportado por Durgesh Valecha.
Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA