Given three integers N, A, and B, the task is to find a pair of positive integers (a, b) such that Aa + Bb = N.If no such pair exists, print -1.
Examples:
Input: N = 106, A = 3, B = 5
Output: 4 2
Explanation: Pair (4, 2) satisfies the answer i.e., 34+52 is equal to 106Input: N = 60467200, A = 6, B = 4
Output: 10 5
Explanation: Pair (10, 5) satisfies the answer i.e., 610+45 is equal to 60467200
Approach: The idea is to calculate logAN and logBN and check for every pair (i, j) (0 ≤ i ≤ logAN and 0 ≤ j ≤ logBN ), whether Ai + Bj is equal to N or not. Follow the steps below to solve the problem:
- First, find the minimum power of A and B that is greater than N and store it in the variables X and Y respectively.
- Check each pair (i, j) such that 0≤i≤X and 0≤j≤Y, and if Ai + Bj is equal to N, print the pair (i, j).
- Print -1, if no such pair is found.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the minimum // power of A and B greater than N int power( long long int A, long long int N) { // Stores the power of A which // is greater than N int count = 0; if (A == 1) return 0; while (N) { // Increment count by 1 count++; // Divide N by A N /= A; } return count; } // Function to find a pair (a, b) // such that A^a + B^b = N void Pairs( long long int N, long long int A, long long int B) { int powerA, powerB; // Calculate the minimum power // of A greater than N powerA = power(A, N); // Calculate the minimum power // of B greater than N powerB = power(B, N); // Make copy of A and B long long int intialB = B, intialA = A; // Traverse for every pair (i, j) A = 1; for ( int i = 0; i <= powerA; i++) { B = 1; for ( int j = 0; j <= powerB; j++) { // Check if B^j + A^i = N // To overcome the overflow problem // use B=N-A rather than B+A=N if (B == N - A) { cout << i << " " << j << endl; return ; } // Increment power B by 1 B *= intialB; } // Increment power A by 1 A *= intialA; } // Finally print -1 if no pair // is found cout << -1 << endl; return ; } // Driver Code int main() { // Given A, B and N long long int N = 106, A = 3, B = 5; // Function Call Pairs(N, A, B); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ // Function to calculate the minimum // power of A and B greater than N static int power( int A, int N) { // Stores the power of A which // is greater than N int count = 0 ; if (A == 1 ) return 0 ; while (N > 0 ) { // Increment count by 1 count++; // Divide N by A N /= A; } return count; } // Function to find a pair (a, b) // such that A^a + B^b = N static void Pairs( int N, int A, int B) { int powerA, powerB; // Calculate the minimum power // of A greater than N powerA = power(A, N); // Calculate the minimum power // of B greater than N powerB = power(B, N); // Make copy of A and B int intialB = B, intialA = A; // Traverse for every pair (i, j) A = 1 ; for ( int i = 0 ; i <= powerA; i++) { B = 1 ; for ( int j = 0 ; j <= powerB; j++) { // Check if B^j + A^i = N // To overcome the overflow problem // use B=N-A rather than B+A=N if (B == N - A) { System.out.println(i + " " + j); return ; } // Increment power B by 1 B *= intialB; } // Increment power A by 1 A *= intialA; } // Finally print -1 if no pair // is found System.out.println( "-1" ); return ; } // Driver Code public static void main(String args[]) { // Given A, B and N int N = 106 , A = 3 , B = 5 ; // Function Call Pairs(N, A, B); } } // This code is contributed by 18bhupenderyadav18 |
Python3
# Python program for the above approach # Function to calculate the minimum # power of A and B greater than N def power(A, N): # Stores the power of A which # is greater than N count = 0 ; if (A = = 1 ): return 0 ; while (N > 0 ): # Increment count by 1 count + = 1 ; # Divide N by A N / / = A; return int (count); # Function to find a pair (a, b) # such that A^a + B^b = N def Pairs(N, A, B): powerA, powerB = 0 , 0 ; # Calculate the minimum power # of A greater than N powerA = power(A, N); # Calculate the minimum power # of B greater than N powerB = power(B, N); # Make copy of A and B intialB = B; intialA = A; # Traverse for every pair (i, j) A = 1 ; for i in range (powerA + 1 ): B = 1 ; for j in range (powerB + 1 ): # Check if B^j + A^i = N # To overcome the overflow problem # use B=N-A rather than B+A=N if (B = = N - A): print (i , " " , j); return ; # Increment power B by 1 B * = intialB; # Increment power A by 1 A * = intialA; # Finally pr-1 if no pair # is found print ( "-1" ); return ; # Driver Code if __name__ = = '__main__' : # Given A, B and N N = 106 ; A = 3 ; B = 5 ; # Function Call Pairs(N, A, B); # This code is contributed by 29AjayKumar |
C#
// C# program for the above approach using System; class GFG { // Function to calculate the minimum // power of A and B greater than N static int power( int A, int N) { // Stores the power of A which // is greater than N int count = 0; if (A == 1) return 0; while (N > 0) { // Increment count by 1 count++; // Divide N by A N /= A; } return count; } // Function to find a pair (a, b) // such that A^a + B^b = N static void Pairs( int N, int A, int B) { int powerA, powerB; // Calculate the minimum power // of A greater than N powerA = power(A, N); // Calculate the minimum power // of B greater than N powerB = power(B, N); // Make copy of A and B int intialB = B, intialA = A; // Traverse for every pair (i, j) A = 1; for ( int i = 0; i <= powerA; i++) { B = 1; for ( int j = 0; j <= powerB; j++) { // Check if B^j + A^i = N // To overcome the overflow problem // use B=N-A rather than B+A=N if (B == N - A) { Console.WriteLine(i + " " + j); return ; } // Increment power B by 1 B *= intialB; } // Increment power A by 1 A *= intialA; } // Finally print -1 if no pair // is found Console.WriteLine( "-1" ); return ; } // Driver Code public static void Main(String []args) { // Given A, B and N int N = 106, A = 3, B = 5; // Function Call Pairs(N, A, B); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Function to calculate the minimum // power of A and B greater than N function power(A, N) { // Stores the power of A which // is greater than N let count = 0; if (A == 1) return 0; while (N > 0) { // Increment count by 1 count++; // Divide N by A N /= A; } return count; } // Function to find a pair (a, b) // such that A^a + B^b = N function Pairs(N, A, B) { let powerA, powerB; // Calculate the minimum power // of A greater than N powerA = power(A, N); // Calculate the minimum power // of B greater than N powerB = power(B, N); // Make copy of A and B let letialB = B, letialA = A; // Traverse for every pair (i, j) A = 1; for (let i = 0; i <= powerA; i++) { B = 1; for (let j = 0; j <= powerB; j++) { // Check if B^j + A^i = N // To overcome the overflow problem // use B=N-A rather than B+A=N if (B == N - A) { document.write(i + " " + j); return ; } // Increment power B by 1 B *= letialB; } // Increment power A by 1 A *= letialA; } // Finally print -1 if no pair // is found document.write( "-1" ); return ; } // driver function // Given A, B and N let N = 106, A = 3, B = 5; // Function Call Pairs(N, A, B); // This code is contributed by splevel62. </script> |
4 2
Time Complexity: O((logAN)*(logBN))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!