Dado un entero positivo N , la tarea es comprobar si el número dado N se puede representar como la suma de las distintas potencias de 3 . Si se encuentra que es cierto, escriba «Sí» . De lo contrario, “No” .
Ejemplos:
Entrada: N =28
Salida: Sí
Explicación:
El número N(= 28) se puede representar (1 + 7) = (3 0 + 3 3 ), que es una potencia perfecta 2.Entrada: N = 6
Salida: No
Enfoque: El enfoque más simple para resolver el problema dado es generar todas las permutaciones posibles de todas las distintas potencias de 3 y si existe tal combinación cuya suma sea una potencia de 3 perfecta . Como 3 15 > 10 7 entonces solo hay 16 potencias distintas, es decir, [0, 15] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to try all permutations
// of distinct powers
bool PermuteAndFind(vector<long> power, int idx,
long SumSoFar, int target)
{
// Base Case
if (idx == power.size()) {
// If the distinct powers
// sum is obtained
if (SumSoFar == target)
return true;
// Otherwise
return false;
}
// If current element not selected
// in power[]
bool select
= PermuteAndFind(power, idx + 1, SumSoFar, target);
// If current element selected in
// power[]
bool notselect = PermuteAndFind(
power, idx + 1, SumSoFar + power[idx], target);
// Return 1 if any permutation
// found
return (select || notselect);
}
// Function to check the N can be
// represented as the sum of the
// distinct powers of 3
void DistinctPowersOf3(int N)
{
// Stores the all distincts powers
// of three to [0, 15]
vector<long> power(16);
power[0] = 1;
for (int i = 1; i < 16; i++)
power[i] = 3 * power[i - 1];
// Function Call
bool found = PermuteAndFind(power, 0, 0L, N);
// print
if (found == true) {
cout << "Yes";
}
else {
cout << "No";
}
}
// Driven Code
int main()
{
int N = 91;
DistinctPowersOf3(N);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to try all permutations
// of distinct powers
public static boolean PermuteAndFind(int[] power, int idx,
int SumSoFar, int target)
{
// Base Case
if (idx == power.length)
{
// If the distinct powers
// sum is obtained
if (SumSoFar == target)
return true;
// Otherwise
return false;
}
// If current element not selected
// in power[]
boolean select = PermuteAndFind(power, idx + 1, SumSoFar, target);
// If current element selected in
// power[]
boolean notselect = PermuteAndFind(power, idx + 1, SumSoFar + power[idx], target);
// Return 1 if any permutation
// found
return (select || notselect);
}
// Function to check the N can be
// represented as the sum of the
// distinct powers of 3
public static void DistinctPowersOf3(int N)
{
// Stores the all distincts powers
// of three to [0, 15]
int[] power = new int[16];
power[0] = 1;
for (int i = 1; i < 16; i++)
power[i] = 3 * power[i - 1];
// Function Call
boolean found = PermuteAndFind(power, 0, 0, N);
// print
if (found == true) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
// Driven Code
public static void main(String args[]) {
int N = 91;
DistinctPowersOf3(N);
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python3 program for the above approach
# Function to try all permutations
# of distinct powers
def PermuteAndFind(power, idx, SumSoFar, target):
# Base Case
if (idx == len(power)):
# If the distinct powers
# sum is obtained
if (SumSoFar == target):
return True
# Otherwise
return False
# If current element not selected
# in power[]
select = PermuteAndFind(power, idx + 1,
SumSoFar, target)
# If current element selected in
# power[]
notselect = PermuteAndFind(power, idx + 1,
SumSoFar + power[idx],
target)
# Return 1 if any permutation
# found
return(select or notselect)
# Function to check the N can be
# represented as the sum of the
# distinct powers of 3
def DistinctPowersOf3(N):
# Stores the all distincts powers
# of three to[0, 15]
power = [0 for x in range(16)]
power[0] = 1
for i in range(1, 16):
power[i] = 3 * power[i - 1]
# Function Call
found = PermuteAndFind(power, 0, 0, N)
# Print
if (found == True):
print("Yes")
else:
print("No")
# Driver Code
N = 91
DistinctPowersOf3(N)
# This code is contributed by amreshkumar3
C#
// C# program for the above approach
using System;
class GFG{
// Function to try all permutations
// of distinct powers
public static bool PermuteAndFind(int[] power, int idx,
int SumSoFar, int target)
{
// Base Case
if (idx == power.Length)
{
// If the distinct powers
// sum is obtained
if (SumSoFar == target)
return true;
// Otherwise
return false;
}
// If current element not selected
// in power[]
bool select = PermuteAndFind(power, idx + 1, SumSoFar, target);
// If current element selected in
// power[]
bool notselect = PermuteAndFind(power, idx + 1, SumSoFar + power[idx], target);
// Return 1 if any permutation
// found
return (select || notselect);
}
// Function to check the N can be
// represented as the sum of the
// distinct powers of 3
public static void DistinctPowersOf3(int N)
{
// Stores the all distincts powers
// of three to [0, 15]
int[] power = new int[16];
power[0] = 1;
for (int i = 1; i < 16; i++)
power[i] = 3 * power[i - 1];
// Function Call
bool found = PermuteAndFind(power, 0, 0, N);
// print
if (found == true) {
Console.Write("Yes");
} else {
Console.Write("No");
}
}
// Driver Code
public static void Main()
{
int N = 91;
DistinctPowersOf3(N);
}
}
// This code is contributed by avijitmondal1998.
Javascript
<script>
// Javascript program for the above approach
// Function to try all permutations
// of distinct powers
function PermuteAndFind(power, idx, SumSoFar, target) {
// Base Case
if (idx == power.length) {
// If the distinct powers
// sum is obtained
if (SumSoFar == target) return true;
// Otherwise
return false;
}
// If current element not selected
// in power[]
let select = PermuteAndFind(power, idx + 1, SumSoFar, target);
// If current element selected in
// power[]
let notselect = PermuteAndFind(power, idx + 1, SumSoFar + power[idx], target);
// Return 1 if any permutation
// found
return select || notselect;
}
// Function to check the N can be
// represented as the sum of the
// distinct powers of 3
function DistinctPowersOf3(N) {
// Stores the all distincts powers
// of three to [0, 15]
let power = new Array(16);
power[0] = 1;
for (let i = 1; i < 16; i++) power[i] = 3 * power[i - 1];
// Function Call
let found = PermuteAndFind(power, 0, 0, N);
// print
if (found == true) {
document.write("Yes");
} else {
document.write("No");
}
}
// Driven Code
let N = 91;
DistinctPowersOf3(N);
</script>
Producción
Yes
Complejidad de Tiempo: O(2 N )
Espacio Auxiliar: O(2 N )
Otro enfoque: el enfoque anterior también se puede optimizar observando el hecho de que N está en forma ternaria ( Base 3 ). Cada dígito es 3 i , y el número ternario (N) es la suma de ellos.
Para tener distintas potencias de 3 , para sumar N, en forma ternaria, el i -ésimo dígito puede ser 0, 1 o 2 (en binario, es 0 y 1). Por lo tanto, puede haber tres casos para cada dígito en la i-ésima posición :
- El dígito puede ser 0 , es decir, no hay 3 i número en N.
- El dígito puede ser 1 , es decir, hay un número de 3 i en N.
- El dígito no puede ser 2 porque entonces hay 2 de 3 i , por lo tanto, no distintos .
Siga los pasos a continuación para resolver el problema:
- Iterar hasta que N se convierta en 0 y realizar los siguientes pasos:
- Si el valor de N%3 es 2 , imprima “No” .
- De lo contrario, divida N entre 3 .
- Después de completar los pasos anteriores, si el valor de N es 0 , imprima «Sí» . De lo contrario, “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether the given
// N can be represented as the sum of
// the distinct powers of 3
void DistinctPowersOf3(int N)
{
// Iterate until N is non-zero
while (N > 0) {
// Termination Condition
if (N % 3 == 2) {
cout << "No";
return;
}
// Right shift ternary bits
// by 1 for the next digit
N /= 3;
}
// If N can be expressed as the
// sum of perfect powers of 3
cout << "Yes";
}
// Driver Code
int main()
{
int N = 91;
DistinctPowersOf3(N);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to check whether the given
// N can be represented as the sum of
// the distinct powers of 3
public static void DistinctPowersOf3(int N)
{
// Iterate until N is non-zero
while (N > 0) {
// Termination Condition
if (N % 3 == 2) {
System.out.println("No");
return;
}
// Right shift ternary bits
// by 1 for the next digit
N /= 3;
}
// If N can be expressed as the
// sum of perfect powers of 3
System.out.println("Yes");
}
// Driver Code
public static void main(String args[])
{
int N = 91;
DistinctPowersOf3(N);
}
}
// This code is contributed by _saurabh_jaiswal.
Python3
# Python3 program for the above approach
# Function to check whether the given
# N can be represented as the sum of
# the distinct powers of 3
def DistinctPowersOf3(N):
# Iterate until N is non-zero
while (N > 0):
# Termination Condition
if (N % 3 == 2):
cout << "No"
return
# Right shift ternary bits
# by 1 for the next digit
N //= 3
# If N can be expressed as the
# sum of perfect powers of 3
print ("Yes")
# Driver Code
if __name__ == '__main__':
N = 91
DistinctPowersOf3(N)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check whether the given
// N can be represented as the sum of
// the distinct powers of 3
static void DistinctPowersOf3(int N)
{
// Iterate until N is non-zero
while (N > 0) {
// Termination Condition
if (N % 3 == 2) {
Console.Write("No");
return;
}
// Right shift ternary bits
// by 1 for the next digit
N /= 3;
}
// If N can be expressed as the
// sum of perfect powers of 3
Console.Write("Yes");
}
// Driver Code
public static void Main()
{
int N = 91;
DistinctPowersOf3(N);
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
// Function to check whether the given
// N can be represented as the sum of
// the distinct powers of 3
function DistinctPowersOf3(N)
{
// Iterate until N is non-zero
while (N > 0) {
// Termination Condition
if (N % 3 == 2)
{
document.write("No");
return;
}
// Right shift ternary bits
// by 1 for the next digit
N = Math.floor(N/ 3);
}
// If N can be expressed as the
// sum of perfect powers of 3
document.write("Yes");
}
// Driver Code
let N = 91;
DistinctPowersOf3(N);
// This code is contributed by patel2127
</script>
Producción
Yes
Complejidad temporal: O(log 3 N)
Espacio auxiliar: O(1)