Given two numbers w and m, we need to determine whether it is possible to represent m in terms of powers of w. The powers of number w can be added or subtracted to obtain m and each powers of w can be used only once .
Examples:
Input : 3 7
Output : Yes
As 7 = 9 - 3 + 1 (3^2 - 3^1 + 3^0 )
so it is possible .
Input : 100 50
Output : No
As 50 is less than 100 so we can never
represent it in the powers of 100 .
Here we have to represent m in terms of powers of w used only once so it can be shown through the following equation .
c0 + c1*w^1 + c2*w^2 + β¦ = m ββ (Equation 1)
Where each c0, c1, c2 β¦ are either -1 (for subtracting that power of w ), 0 (not using that power of w ), 1 (for adding that power of w ) .
=> c1*w^1 + c2*w^2 + β¦ = m β c0
=> w(c1 + c2*w^1 + c3*w^2 + β¦ ) = m β c0
=> c1 + c2*w^1 + c3*w^2 + β¦ = (m β c0)/w ββ (Equation 2)
Now, notice equation 1 and equation 2 β we are trying to solve the same problem all over again. So we have to recurse till m > 0 . For such a solution to exist (m β ci) must be a multiple of w, where ci is the coefficient of the equation . The ci can be -1, 0, 1 . So we have to check for all three possibilities ( ( m β 1 ) % w == 0), ( ( m + 1 ) % w == 0) and ( m % w == 0) . If it is not, then there will not be any solution.
C++
#include <bits/stdc++.h>
using namespace std;
bool asPowerSum( int w, int m)
{
while (m) {
if ((m - 1) % w == 0)
m = (m - 1) / w;
else if ((m + 1) % w == 0)
m = (m + 1) / w;
else if (m % w == 0)
m = m / w;
else
break ;
}
return (m == 0);
}
int main()
{
int w = 3, m = 7;
if (asPowerSum(w, m))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
|
Java
class GFG
{
static boolean asPowerSum( int w, int m)
{
while (m > 0 )
{
if ((m - 1 ) % w == 0 )
m = (m - 1 ) / w;
else if ((m + 1 ) % w == 0 )
m = (m + 1 ) / w;
else if (m % w == 0 )
m = m / w;
else
break ;
}
return (m == 0 );
}
public static void main (String[] args)
{
int w = 3 , m = 7 ;
if (asPowerSum(w, m))
System.out.println( "Yes" );
else
System.out.println( "No" );
}
}
|
Python3
def asPowerSum(w, m):
while (m > 0 ):
if ((m - 1 ) % w = = 0 ):
m = (m - 1 ) / w;
elif ((m + 1 ) % w = = 0 ):
m = (m + 1 ) / w;
elif (m % w = = 0 ):
m = m / w;
else :
break ;
return (m = = 0 );
w = 3 ;
m = 7 ;
if (asPowerSum(w, m)):
print ( "Yes" );
else :
print ( "No" );
|
C#
using System;
class GFG
{
static bool asPowerSum( int w,
int m)
{
while (m > 0)
{
if ((m - 1) % w == 0)
m = (m - 1) / w;
else if ((m + 1) % w == 0)
m = (m + 1) / w;
else if (m % w == 0)
m = m / w;
else
break ;
}
return (m == 0);
}
static public void Main ()
{
int w = 3, m = 7;
if (asPowerSum(w, m))
Console.WriteLine( "Yes" );
else
Console.WriteLine( "No" );
}
}
|
PHP
<?php
function asPowerSum( $w , $m )
{
while ( $m )
{
if (( $m - 1) % $w == 0)
$m = ( $m - 1) / $w ;
else if (( $m + 1) % $w == 0)
$m = ( $m + 1) / $w ;
else if ( $m % $w == 0)
$m = $m / $w ;
else
break ;
}
return ( $m == 0);
}
$w = 3;
$m = 7;
if (asPowerSum( $w , $m ))
echo "Yes\n" ;
else
echo "No\n" ;
?>
|
Javascript
<script>
function asPowerSum(w, m)
{
while (m > 0)
{
if ((m - 1) % w == 0)
m = (m - 1) / w;
else if ((m + 1) % w == 0)
m = (m + 1) / w;
else if (m % w == 0)
m = m / w;
else
break ;
}
return (m == 0);
}
let w = 3, m = 7;
if (asPowerSum(w, m))
document.write( "Yes" );
else
document.write( "No" );
</script>
|
Time complexity: O(m)
Auxiliary space: O(1)