Permutation of a number whose sum with the original number is equal to another given number
Given two integers A and C, the task is to check if there exists a permutation of the number A such that the sum of the number A and its permutation is equal to C.
Examples:
Input: A = 133, C = 446
Output: Yes
Explanation: One of the permutation of A is 313. Therefore, sum = 133 + 313 = 446, which is equal to C.Input: A = 200, C = 201
Output: No
Naive Approach: The simplest approach to solve the problem is to generate all permutations of the number A and add it with the original value of A. Now, check if their sum is equal to C or not.
Time Complexity: O((log10A)!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to subtract the value of A from C and check if there exists a permutation of A which is equal to the difference between C and A or not. Follow the steps below to solve the problem:
- Subtract A from C and check if C is less than 0 or not. If found to be true, then print “No”.
- Otherwise, perform the following steps:
- Convert A to its equivalent string representation and store it in a variable, say S.
- Convert C to its equivalent string representation and store it in a variable, say K.
- Sort the newly generated strings S and K.
- If S is equal to K, print “Yes” along with the permutation. Otherwise, print “No”.
Below is the implementation of the above approach:
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> |
Yes 313
Time Complexity: O((log10A)*log (log10A))
Auxiliary Space: O(log10A)