Find a pair ( a , b ) such that Aa + Bb = N | Java program for the above approach ; Function to calculate the minimum power of A and B greater than N ; Stores the power of A which is greater than N ; Increment count by 1 ; Divide N by A ; Function to find a pair ( a , b ) such that A ^ a + B ^ b = N ; Calculate the minimum power of A greater than N ; Calculate the minimum power of B greater than N ; Make copy of A and B ; Traverse for every pair ( i , j ) ; Check if B ^ j + A ^ i = N To overcome the overflow problem use B = N - A rather than B + A = N ; Increment power B by 1 ; Increment power A by 1 ; Finally print - 1 if no pair is found ; Driver Code ; Given A , B and N ; Function Call
import java . io . * ; class GFG { static int power ( int A , int N ) { int count = 0 ; if ( A == 1 ) return 0 ; while ( N > 0 ) { count ++ ; N /= A ; } return count ; } static void Pairs ( int N , int A , int B ) { int powerA , powerB ; powerA = power ( A , N ) ; powerB = power ( B , N ) ; int intialB = B , intialA = A ; A = 1 ; for ( int i = 0 ; i <= powerA ; i ++ ) { B = 1 ; for ( int j = 0 ; j <= powerB ; j ++ ) { if ( B == N - A ) { System . out . println ( i + " ▁ " + j ) ; return ; } B *= intialB ; } A *= intialA ; } System . out . println ( " - 1" ) ; return ; } public static void main ( String args [ ] ) { int N = 106 , A = 3 , B = 5 ; Pairs ( N , A , B ) ; } }