Representation of a number in powers of other

0 0 5 minutes read

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++

// CPP program to check if m can be represented
// as powers of w.
#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; // None of 3 worked.
    }
 
    // If m is not zero means, it can't be 
    // represented in terms of powers of w.
    return (m == 0);
}
 
// Driver code
int main()
{
    int w = 3, m = 7;
    if (asPowerSum(w, m))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
   return 0;
}

Java

// Java program to check if m can 
// be represented as powers of w.
 
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; // None of 3 worked.
        }
     
        // If m is not zero means, it can't be 
        // represented in terms of powers of w.
        return (m == 0);
    } 
     
    // Driver function
    public static void main (String[] args)
    {
        int w = 3, m = 7;
        if (asPowerSum(w, m))
            System.out.println("Yes");
        else
            System.out.println("No"); 
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Python3 program to check if m can 
# be represented as powers of w.
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; # None of 3 worked.
     
    # If m is not zero means, it can't be
    # represented in terms of powers of w.
    return (m == 0);
 
# Driver code
w = 3; 
m = 7;
if (asPowerSum(w, m)):
    print("Yes");
else:
    print("No");
 
# This code is contributed by mits

C#

// C# program to check if 
// m can be represented
// as powers of w.
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; // None of 3 worked.
        }
     
        // If m is not zero means, 
        // it can't be represented
        // in terms of powers of w.
        return (m == 0);
    } 
     
    // Driver Code
    static public void Main ()
    {
        int w = 3, m = 7;
        if (asPowerSum(w, m))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No"); 
    }
}
 
// This code is contributed 
// by akt_mit.

PHP

<?php
// PHP program to check if m can 
// be represented as powers of w.
 
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; // None of 3 worked.
    }
 
    // If m is not zero means, it can't be 
    // represented in terms of powers of w.
    return ($m == 0);
}
 
// Driver code
$w = 3; 
$m = 7;
if (asPowerSum($w, $m))
    echo "Yes\n";
else
    echo "No\n";
 
// This code is contributed by mits
?>

Javascript

<script>
 
// Javascript program to check if m can 
// be represented as powers of w.
 
    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; // None of 3 worked.
        }
       
        // If m is not zero means, it can't be 
        // represented in terms of powers of w.
        return (m == 0);
    } 
     
// Driver code
 
        let w = 3, m = 7;
        if (asPowerSum(w, m))
            document.write("Yes");
        else
            document.write("No");
       
      // This code is contributed by sanjoy_62.
</script>

Output:

Yes

Time complexity: O(m)
Auxiliary space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!