Dado un número positivo N , tenemos que encontrar si N se puede convertir a la forma K K donde K también es un número entero positivo, usando la siguiente operación cualquier número de veces:
- Elija cualquier dígito menor que el valor actual de N, digamos d.
- N = N – d 2 , cambia N cada vez
Si es posible expresar el número en la forma requerida, escriba «Sí», de lo contrario, escriba «No».
Ejemplos:
Entrada: N = 13
Salida: Sí
Explicación:
Para el entero 13 elija d = 3 : N = 13 – 3 2 = 4, 4 tiene la forma 2 2 . Por lo tanto, la salida es 4.Entrada: N = 90
Salida: No
Explicación:
No es posible expresar el número 90 en la forma requerida.
Enfoque ingenuo:
para resolver el problema mencionado anteriormente, utilizaremos Recursion . En cada paso recursivo, recorra todos los dígitos del valor actual de N y elíjalo como d. De esta forma se explorarán todos los espacios de búsqueda y si en alguno de ellos N resulta ser de la forma K K detiene la recursión y devuelve verdadero. Para verificar si el número tiene la forma dada, almacene previamente todos esos números en un conjunto. Este método toma O(D N ) , donde D es el número de dígitos en N tiempo y se puede optimizar aún más.
A continuación se muestra la implementación del enfoque dado:
C++14
// C++ implementation to Check whether a given
// number N can be converted to the form K
// power K by the given operation
#include <bits/stdc++.h>
using namespace std;
unordered_set<int> kPowKform;
// Function to check if N can
// be converted to K power K
int func(int n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.count(n))
return 1;
int answer = 0;
int x = n;
// Iterate through each digit of n
while (x > 0) {
int d = x % 10;
if (d != 0) {
// Check if it is possible to
// obtain number of given form
if (func(n - d * d)) {
answer = 1;
break;
}
}
// Reduce the number each time
x /= 10;
}
// Return the result
return answer;
}
// Function to check the above method
void canBeConverted(int n)
{
// Check if conversion if possible
if (func(n))
cout << "Yes";
else
cout << "No";
}
// Driver code
int main()
{
int N = 90;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for (int i = 1; i <= 8; i++) {
int val = 1;
for (int j = 1; j <= i; j++)
val *= i;
kPowKform.insert(val);
}
canBeConverted(N);
return 0;
}
Java
// Java implementation to
// Check whether a given
// number N can be converted
// to the form K power K by
// the given operation
import java.util.*;
class GFG{
static HashSet<Integer> kPowKform =
new HashSet<Integer>();
// Function to check if N can
// be converted to K power K
static int func(int n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.contains(n))
return 1;
int answer = 0;
int x = n;
// Iterate through
// each digit of n
while (x > 0)
{
int d = x % 10;
if (d != 0)
{
// Check if it is possible to
// obtain number of given form
if (func(n - d * d) == 1)
{
answer = 1;
break;
}
}
// Reduce the number each time
x /= 10;
}
// Return the result
return answer;
}
// Function to check the above method
static void canBeConverted(int n)
{
// Check if conversion if possible
if (func(n) == 1)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
int N = 90;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for (int i = 1; i <= 8; i++)
{
int val = 1;
for (int j = 1; j <= i; j++)
val *= i;
kPowKform.add(val);
}
canBeConverted(N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to Check whether a given
# number N can be converted to the form K
# power K by the given operation
kPowKform=dict()
# Function to check if N can
# be converted to K power K
def func(n):
global kPowKform
if (n <= 0):
return 0
# Check if n is of the form k^k
if (n in kPowKform):
return 1
answer = 0
x = n
# Iterate through each digit of n
while (x > 0):
d = x % 10
if (d != 0):
# Check if it is possible to
# obtain number of given form
if (func(n - d * d)):
answer = 1
break
# Reduce the number each time
x //= 10
# Return the result
return answer
# Function to check the above method
def canBeConverted(n):
# Check if conversion if possible
if (func(n)):
print("Yes")
else:
print("No")
# Driver code
if __name__ == '__main__':
N = 90
# Pre store K power K form of numbers
# Loop till 8, because 8^8 > 10^7
for i in range(1,9):
val = 1
for j in range(1,i+1):
val *= i
kPowKform[val]=1
canBeConverted(N)
# This code is contributed by mohit kumar 29
C#
// C# implementation to check whether a given
// number N can be converted to the form K
// power K by the given operation
using System;
using System.Collections.Generic;
class GFG{
static SortedSet<int> kPowKform = new SortedSet<int>();
// Function to check if N can
// be converted to K power K
static int func(int n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.Contains(n))
return 1;
int answer = 0;
int x = n;
// Iterate through each digit of n
while (x > 0)
{
int d = x % 10;
if (d != 0)
{
// Check if it is possible to
// obtain number of given form
if (func(n - d * d) == 1)
{
answer = 1;
break;
}
}
// Reduce the number each time
x /= 10;
}
// Return the result
return answer;
}
// Function to check the above method
static void canBeConverted(int n)
{
// Check if conversion if possible
if (func(n) == 1)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main()
{
int N = 90;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for(int i = 1; i <= 8; i++)
{
int val = 1;
for(int j = 1; j <= i; j++)
val *= i;
kPowKform.Add(val);
}
canBeConverted(N);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript implementation to Check whether a given
// number N can be converted to the form K
// power K by the given operation
var kPowKform = new Set();
// Function to check if N can
// be converted to K power K
function func(n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.has(n))
return 1;
var answer = 0;
var x = n;
// Iterate through each digit of n
while (x > 0)
{
var d = x % 10;
if (d != 0)
{
// Check if it is possible to
// obtain number of given form
if (func(n - d * d)) {
answer = 1;
break;
}
}
// Reduce the number each time
x = parseInt(x/10);
}
// Return the result
return answer;
}
// Function to check the above method
function canBeConverted(n)
{
// Check if conversion if possible
if (func(n))
document.write( "Yes");
else
document.write( "No");
}
// Driver code
var N = 90;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for (var i = 1; i <= 8; i++) {
var val = 1;
for (var j = 1; j <= i; j++)
val *= i;
kPowKform.add(val);
}
canBeConverted(N);
// This code is contributed by noob2000.
</script>
Producción:
No
Enfoque eficiente:
en el enfoque recursivo, estamos resolviendo el mismo subproblema varias veces, es decir, hay subproblemas superpuestos . Entonces podemos usar Programación Dinámica y memorizar el enfoque recursivo usando un caché o tabla de memorización.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Check whether a given
// number N can be converted to the form K
// power K by the given operation
#include <bits/stdc++.h>
using namespace std;
unordered_set<int> kPowKform;
int dp[100005];
// Function to check if a number is converatable
int func(int n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.count(n))
return 1;
// Check if the subproblem has been solved before
if (dp[n] != -1)
return dp[n];
int answer = 0;
int x = n;
// Iterate through each digit of n
while (x > 0) {
int d = x % 10;
if (d != 0) {
// Check if it is possible to
// obtain number of given form
if (func(n - d * d)) {
answer = 1;
break;
}
}
// Reduce the number each time
x /= 10;
}
// Store and return the
// answer to this subproblem
return dp[n] = answer;
}
// Function to check the above method
void canBeConverted(int n)
{
// Initialise the dp table
memset(dp, -1, sizeof(dp));
// Check if conversion if possible
if (func(n))
cout << "Yes";
else
cout << "No";
}
// Driver code
int main()
{
int N = 13;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for (int i = 1; i <= 8; i++) {
int val = 1;
for (int j = 1; j <= i; j++)
val *= i;
kPowKform.insert(val);
}
canBeConverted(N);
return 0;
}
Java
// Java implementation to
// Check whether a given
// number N can be converted
// to the form K power K by
// the given operation
import java.util.*;
class GFG{
static HashSet<Integer> kPowKform =
new HashSet<>();
static int []dp = new int[100005];
// Function to check if
// a number is converatable
static int func(int n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.contains(n))
return 1;
// Check if the subproblem
// has been solved before
if (dp[n] != -1)
return dp[n];
int answer = 0;
int x = n;
// Iterate through each digit of n
while (x > 0)
{
int d = x % 10;
if (d != 0)
{
// Check if it is possible to
// obtain number of given form
if (func(n - d * d) != 0)
{
answer = 1;
break;
}
}
// Reduce the number
// each time
x /= 10;
}
// Store and return the
// answer to this subproblem
return dp[n] = answer;
}
// Function to check the above method
static void canBeConverted(int n)
{
// Initialise the dp table
for (int i = 0; i < n; i++)
dp[i] = -1;
// Check if conversion if possible
if (func(n) == 0)
System.out.print("Yes");
else
System.out.print("No");
}
// Driver code
public static void main(String[] args)
{
int N = 13;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for (int i = 1; i <= 8; i++)
{
int val = 1;
for (int j = 1; j <= i; j++)
val *= i;
kPowKform.add(val);
}
canBeConverted(N);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to check whether
# a given number N can be converted to
# the form K power K by the given operation
kPowKform = dict()
# Function to check if N can
# be converted to K power K
def func(n, dp):
global kPowKform
if (n <= 0):
return 0
# Check if n is of the form k^k
if (n in kPowKform):
return 1
if (dp[n] != -1):
return dp[n]
answer = 0
x = n
# Iterate through each digit of n
while (x > 0):
d = x % 10
if (d != 0):
# Check if it is possible to
# obtain number of given form
if (func(n - d * d, dp)):
answer = 1
break
# Reduce the number each time
x //= 10
dp[n] = answer
# Return the result
return answer
# Function to check the above method
def canBeConverted(n):
dp = [-1 for i in range(10001)]
# Check if conversion if possible
if (func(n, dp)):
print("Yes")
else:
print("No")
# Driver code
if __name__ == '__main__':
N = 13
# Pre store K power K form of
# numbers Loop till 8, because
# 8^8 > 10^7
for i in range(1, 9):
val = 1
for j in range(1, i + 1):
val *= i
kPowKform[val] = 1
canBeConverted(N)
# This code is contributed by grand_master
C#
// C# implementation to check whether a given
// number N can be converted to the form K
// power K by the given operation
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
static HashSet<int> kPowKform = new HashSet<int>();
static int []dp = new int[100005];
// Function to check if a number
// is converatable
static int func(int n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.Contains(n))
return 1;
// Check if the subproblem has
// been solved before
if (dp[n] != -1)
return dp[n];
int answer = 0;
int x = n;
// Iterate through each digit of n
while (x > 0)
{
int d = x % 10;
if (d != 0)
{
// Check if it is possible to
// obtain number of given form
if (func(n - d * d) != 0)
{
answer = 1;
break;
}
}
// Reduce the number each time
x /= 10;
}
// Store and return the
// answer to this subproblem
dp[n] = answer;
return answer;
}
// Function to check the above method
static void canBeConverted(int n)
{
// Initialise the dp table
Array.Fill(dp, -1);
// Check if conversion if possible
if (func(n) != 0)
Console.Write("Yes");
else
Console.Write("No");
}
// Driver code
public static void Main(string[] args)
{
int N = 13;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for(int i = 1; i <= 8; i++)
{
int val = 1;
for(int j = 1; j <= i; j++)
val *= i;
kPowKform.Add(val);
}
canBeConverted(N);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to Check whether a given
// number N can be converted to the form K
// power K by the given operation
var kPowKform = new Set();
var dp = Array(100005);
// Function to check if a number is converatable
function func(n)
{
if (n <= 0)
return 0;
// Check if n is of the form k^k
if (kPowKform.has(n))
return 1;
// Check if the subproblem has been solved before
if (dp[n] != -1)
return dp[n];
var answer = 0;
var x = n;
// Iterate through each digit of n
while (x > 0) {
var d = x % 10;
if (d != 0) {
// Check if it is possible to
// obtain number of given form
if (func(n - d * d)) {
answer = 1;
break;
}
}
// Reduce the number each time
x /= 10;
}
// Store and return the
// answer to this subproblem
return dp[n] = answer;
}
// Function to check the above method
function canBeConverted(n)
{
// Initialise the dp table
dp = Array(100005).fill(-1);
// Check if conversion if possible
if (func(n))
document.write( "Yes");
else
document.write( "No");
}
// Driver code
var N = 13;
// Pre store K power K form of numbers
// Loop till 8, because 8^8 > 10^7
for (var i = 1; i <= 8; i++) {
var val = 1;
for (var j = 1; j <= i; j++)
val *= i;
kPowKform.add(val);
}
canBeConverted(N);
// This code is contributed by famously.
</script>
Producción:
Yes
Complejidad de tiempo: O(D * N) , donde D es el número de dígitos en N.