Dados dos enteros A y C , la tarea es comprobar si existe una permutación del número A tal que la suma del número A y su permutación sea igual a C .
Ejemplos:
Entrada: A = 133, C = 446
Salida: Sí
Explicación: Una de las permutaciones de A es 313. Por lo tanto, suma = 133 + 313 = 446, que es igual a C.Entrada: A = 200, C = 201
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las permutaciones del número A y agregarlo con el valor original de A . Ahora, comprueba si su suma es igual a C o no.
Complejidad de Tiempo: O((log 10 A)!)
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es restar el valor de A de C y verificar si existe una permutación de A que sea igual a la diferencia entre C y A o no. Siga los pasos a continuación para resolver el problema:
- Resta A de C y comprueba si C es menor que 0 o no. Si se encuentra que es cierto, escriba «No».
- De lo contrario, realice los siguientes pasos:
- Convierta A a su representación de string equivalente y guárdela en una variable, digamos S .
- Convierta C a su representación de string equivalente y guárdela en una variable, digamos K .
- Ordene las strings S y K recién generadas .
- Si S es igual a K , imprime «Sí» junto con la permutación. De lo contrario, escriba “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 if there
// exists a permutation of a number
// A whose sum with A results to C
void checkPermutation(int a, int c)
{
// Subtract a from c
c -= a;
// Check if c is less than 0
if (c <= 0) {
// If true, print "No"
cout << "No";
return;
}
// Otherwise, convert a to its
// equivalent string
string s = to_string(a);
// convert c to its
// equivalent string
string k = to_string(c);
// Sort string s
sort(s.begin(), s.end());
// Sort string k
sort(k.begin(), k.end());
// If both strings are equal,
// then print "Yes"
if (k == s) {
cout << "Yes\n"
<< c;
}
// Otherwise, print "No"
else {
cout << "No";
}
}
// Driver Code
int main()
{
int A = 133, C = 446;
checkPermutation(A, C);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if there
// exists a permutation of a number
// A whose sum with A results to C
static void checkPermutation(int a, int c)
{
// Subtract a from c
c -= a;
// Check if c is less than 0
if (c <= 0)
{
// If true, print "No"
System.out.println("No");
return;
}
// Otherwise, convert a to its
// equivalent string
String s = sortString(Integer.toString(a));
// Convert c to its
// equivalent string
String k = sortString(Integer.toString(c));
// If both strings are equal,
// then print "Yes"
if (k.equals(s))
{
System.out.println("Yes");
System.out.println(c);
}
// Otherwise, print "No"
else
{
System.out.println("No");
}
}
// Method to sort a string alphabetically
public static String sortString(String inputString)
{
// Convert input string to char array
char tempArray[] = inputString.toCharArray();
// sort tempArray
Arrays.sort(tempArray);
// Return new sorted string
return new String(tempArray);
}
// Driver code
public static void main(String[] args)
{
int A = 133, C = 446;
checkPermutation(A, C);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to check if there
# exists a permutation of a number
# A whose sum with A results to C
def checkPermutation(a, c):
# Subtract a from c
c -= a
# Check if c is less than 0
if (c <= 0):
# If true, print "No"
print("No")
return
# Otherwise, convert a to its
# equivalent string
s = str(a)
# convert c to its
# equivalent string
k = str(c)
res = ''.join(sorted(s))
# Sort string s
s = str(res)
# Sort string k
res = ''.join(sorted(k))
k = str(res)
# If both strings are equal,
# then print "Yes"
if (k == s):
print("Yes")
print(c)
# Otherwise, print "No"
else:
print("No")
# Driver Code
if __name__ == '__main__':
A = 133
C = 446
checkPermutation(A, C)
# This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check if there
// exists a permutation of a number
// A whose sum with A results to C
static void checkPermutation(int a, int c)
{
// Subtract a from c
c -= a;
// Check if c is less than 0
if (c <= 0) {
// If true, print "No"
Console.Write("No");
return;
}
// Otherwise, convert a to its
// equivalent string
string s = a.ToString();
// convert c to its
// equivalent string
string k = c.ToString();
// Sort string s
char[] arr = s.ToCharArray();
Array.Sort(arr);
// Sort string k
char[] brr = k.ToCharArray();
Array.Sort(brr);
// If both strings are equal,
// then print "Yes"
if (String.Join("", brr) == String.Join("", arr)) {
Console.Write("Yes\n" + c);
}
// Otherwise, print "No"
else {
Console.WriteLine("No");
}
}
// Driver Code
public static void Main()
{
int A = 133, C = 446;
checkPermutation(A, C);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// javascript program for the above approach
// Function to check if there
// exists a permutation of a number
// A whose sum with A results to C
function checkPermutation(a, c)
{
// Subtract a from c
c -= a;
// Check if c is less than 0
if (c <= 0) {
// If true, print "No"
print("No");
return;
}
// Otherwise, convert a to its
// equivalent string
var s = a.toString();
// convert c to its
// equivalent string
var k = c.toString();
// Sort string s
s= s.split('').sort((a, b) => a.localeCompare(b)).join('');
// sort(s);
// Sort string k
k = k.split('').sort((a, b) => a.localeCompare(b)).join('');
//sort(k);
// If both strings are equal,
// then print "Yes"
if (k == s) {
document.write("Yes" + "<br>" + c);
}
// Otherwise, print "No"
else {
document.write("No");
}
}
// Driver Code
var A = 133, C = 446;
checkPermutation(A, C);
</script>
Producción:
Yes 313
Complejidad de tiempo: O((log 10 A)*log (log 10 A))
Espacio auxiliar: O(log 10 A)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA