Given two positive integers A and C, the task is to check if a number B exists such that A + B = C and B is an anagram of A. If found to be true, then print “YES”. Otherwise, print “NO”.
Input: A = 123, C = 354
Output: YES
Explanation:
231 is an anagram of A and 123 + 231 = 354
Therefore, the required output is “YES”.Input: A = 123, C = 234
Output: NO
Naive Approach: The simplest approach to solve the problem is to generate all possible permutations of digits of A and check if the sum of A and the current permutation of digits of A is equal to C or not. If found to be true, then print “YES”. Otherwise, if no such permutation is found, print “NO”.
Time Complexity: O(log10(N)!)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
A + B = C
B = C – A
Follow the steps below to solve the problem:
- Check if (C – A) is an anagram of A or not. If found to be true, then print “YES”.
- Otherwise, print “NO”.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if an integer B exists // such that A + B = C and B is an anagram of A void CheckExistsABCAnagramOfA( int A, int C) { int B = C - A; // Stores A in string format string a = to_string(A); // Stores B in string format string b = to_string(B); // Sort both the strings sort(a.begin(), a.end()); sort(b.begin(), b.end()); // Checks if both strings // are equal if (a == b) { cout << "YES\n" ; } else { cout << "NO\n" ; } } // Drivers Code int main() { int A = 123, C = 354; CheckExistsABCAnagramOfA(A, C); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG { // Function to check if an integer B exists // such that A + B = C and B is an anagram of A static void CheckExistsABCAnagramOfA( int A, int C) { int B = C - A; // Stores A in String format String a = String.valueOf(A); // Stores B in String format String b = String.valueOf(B); // Sort both the Strings a = sortString(a); b = sortString(b); // Checks if both Strings // are equal if (a.equals(b)) { System.out.print( "YES\n" ); } else { System.out.print( "NO\n" ); } } 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); } // Drivers Code public static void main(String[] args) { int A = 123 , C = 354 ; CheckExistsABCAnagramOfA(A, C); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program to implement the above # approach # Function to check if an integer B exists # such that A + B = C and B is an anagram of A def CheckExistsABCAnagramOfA(A, C): B = C - A # To convert number to list of integers a = [ int (x) for x in str (A)] # To convert number to list of integers b = [ int (x) for x in str (B)] # Sort both the strings a.sort() b.sort() # Checks if both strings # are equal if (a = = b): print ( "YES" ) else : print ( "NO" ) # Driver Code A = 123 C = 354 CheckExistsABCAnagramOfA(A, C) # This code is contributed by sanjoy_62 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to check if an integer B // exists such that A + B = C and B // is an anagram of A static void CheckExistsABCAnagramOfA( int A, int C) { int B = C - A; // Stores A in String format String a = String.Join( "" , A); // Stores B in String format String b = String.Join( "" , B); // Sort both the Strings a = sortString(a); b = sortString(b); // Checks if both Strings // are equal if (a.Equals(b)) { Console.Write( "YES\n" ); } else { Console.Write( "NO\n" ); } } static String sortString(String inputString) { // Convert input string to char array char []tempArray = inputString.ToCharArray(); // Sort tempArray Array.Sort(tempArray); // Return new sorted string return new String(tempArray); } // Driver Code public static void Main(String[] args) { int A = 123, C = 354; CheckExistsABCAnagramOfA(A, C); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program to implement // the above approach // Function to check if an integer B exists // such that A + B = C and B is an anagram of A function CheckExistsABCAnagramOfA(A, C) { var B = C - A; // Stores A in string format var a = (A.toString()); // Stores B in string format var b = (B.toString()); // Sort both the strings a = a.split( '' ).sort().join( '' ); b = b.split( '' ).sort().join( '' ); // Checks if both strings // are equal if (a == b) { document.write( "YES" ); } else { document.write( "NO" ); } } // Drivers Code var A = 123, C = 354; CheckExistsABCAnagramOfA(A, C); </script> |
YES
Time Complexity: O(log10(A)*log(log10(A)))
Auxiliary Space: O(log10(A))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!