Discover the worth of a quantity raised to its reverse

By
Sohaib
-
0
5
Adv1


Adv2

Enhance Article

Save Article

Like Article

Enhance Article

Save Article

Given a quantity N and its reverse R. The duty is to search out the quantity obtained when the quantity is raised to the facility of its personal reverse. The reply will be very massive, return the end result modulo 109+7.

Examples:

 Enter : N = 2, R = 2
Output: 4
Rationalization: Quantity 2 raised to the facility of its reverse 2 offers 4 which provides 4 in consequence after performing modulo 109+7

Enter : N = 57, R = 75
Output: 262042770
Rationalization: 5775 modulo 109+7 offers us the end result as 262042770

Naive Method:

The best strategy to remedy this drawback may very well be to traverse a loop from 1 to R(reverse) and multiply our reply with N  in every iteration.

Observe the steps talked about beneath to implement the concept:

  • Create a variable (say ans) and initialize it to 1 to retailer the ultimate end result.
  • Then, begin a loop from 1 and it goes until R.
    • Multiply the variable ans with N.
  • Return the end result ans with modulo of 1e9+7.

Under is the implementation of the above strategy.

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

int PowerOfNum(int N, int R)

{

    lengthy lengthy ans = 1, mod = 1e9 + 7;

    for (int i = 1; i <= R; i++) {

        ans *= N;

        ans %= mod;

    }

    return ans;

}

  

int foremost()

{

    int N = 57, R = 75;

  

    

    cout << PowerOfNum(N, R);

  

    return 0;

}

Time Complexity: O(R)
Auxiliary Area: O(1)

Environment friendly Method: Bit Manipulation

The environment friendly method of fixing this drawback may very well be bit manipulation, simply break the issue into small components and remedy them right here the idea of binary exponentiation methodology might be used.

  • Each quantity will be written because the sum of powers of two
  • Traverse via all of the bits of a quantity from LSB (Least Important Bit) to MSB (Most Important Bit) in O(log N) time.

Observe the steps talked about beneath to implement the concept:

  •  First, create a variable (say ans) and initialize it to 1 to retailer the end result.
  •  Then, test if the given reverse quantity is odd or not.
    • If sure, then multiply the reply with pow ans = (ans * pow)%mod.
    • Then, multiply the pow with pow i.e., pow = (pow*pow).
    • Begin shifting proper by R = R/2.
  • Lastly, return the ans as end result.

Under is the implementation of the above strategy

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

lengthy lengthy powerOfNum(int num, int rev)

{

    lengthy lengthy ans = 1;

    lengthy lengthy mod = 1e9 + 7;

    lengthy lengthy pow = num * 1LL;

  

    whereas (rev > 0) {

        

        if (rev & 1) {

            ans = (ans * pow) % mod;

        }

        pow = (pow * pow) % mod;

        

        rev >>= 1;

    }

    return ans;

}

  

int foremost()

{

    int N = 57, R = 75;

  

    

    cout << energy(N, R) << endl;

  

    return 0;

}

Java

  

import java.io.*;

  

class GFG {

  

    

    public static void foremost(String[] args)

    {

        int N = 57, R = 75;

  

        

        System.out.println(energy(N, R));

    }

  

    

    static lengthy energy(int num, int rev)

    {

        lengthy ans = 1;

        lengthy mod = 1000000007, pow = num * 1L;

        whereas (rev > 0) {

  

            

            if (rev % 2 == 1) {

                ans = (ans * pow) % mod;

            }

            pow = (pow * pow) % mod;

  

            

            rev >>= 1;

        }

        return ans;

    }

}

Time Complexity: O(log N)
Auxiliary Area: O(1)

Adv3