Given two numbers N and M(M > 1), the task is to find the highest power of M that divides N.
Examples:
Input: N = 12, M = 2
Output: 2
Explanation: The powers of 2 which divide 12 are 1 and 2 (21 = 2 and 22 = 4 which both divide 12).
The higher power is 2, hence consider 2.Input: N = 500, M = 5
Output: 3.
Naive and Bit Manipulation Approach: The naive approach and bit manipulation approach is already mentioned in the Set 1 of this problem.
Efficient Approach: The task can be solved using a binary search technique over the range [1, logB(A)]. For each value x in the range, check if Mx divides N. Finally, return the largest value possible
Follow the below steps to solve the problem:
- Find the value of logM(N)
- Run binary search in range [1, logM(N)] .
- For each value x, check if Mx divides N, and find the largest such value possible.
Below is the implementation of the above approach.
C++
// C++ program to find the Highest // Power of M that divides N #include <bits/stdc++.h> using namespace std; // Function to find any log(N) base M int log_a_to_base_b( int a, int b) { return log (a) / log (b); } // Function to find the Highest Power // of M which divides N int HighestPower( int N, int M) { int start = 0, end = log_a_to_base_b(N, M); int ans = 0; while (start <= end) { int mid = start + (end - start) / 2; int temp = ( int )( pow (M, mid)); if (N % temp == 0) { ans = mid; start = mid + 1; } else { end = mid - 1; } } return ans; } // Driver code int main() { int N = 12; int M = 2; cout << HighestPower(N, M) << endl; return 0; } |
Java
// Java program to find the Highest // Power of M that divides N import java.util.*; public class GFG { // Function to find any log(N) base M static int log_a_to_base_b( int a, int b) { return ( int )(Math.log(a) / Math.log(b)); } // Function to find the Highest Power // of M which divides N static int HighestPower( int N, int M) { int start = 0 , end = log_a_to_base_b(N, M); int ans = 0 ; while (start <= end) { int mid = start + (end - start) / 2 ; int temp = ( int )(Math.pow(M, mid)); if (N % temp == 0 ) { ans = mid; start = mid + 1 ; } else { end = mid - 1 ; } } return ans; } // Driver code public static void main(String args[]) { int N = 12 ; int M = 2 ; System.out.println(HighestPower(N, M)); } } // This code is contributed by Samim Hossain Mondal. |
Python
# Python program to find the Highest # Power of M that divides N import math # Function to find any log(N) base M def log_a_to_base_b(a, b): return math.log(a) / math.log(b) # Function to find the Highest Power # of M which divides N def HighestPower(N, M): start = 0 end = log_a_to_base_b(N, M) ans = 0 while (start < = end): mid = math.floor(start + (end - start) / 2 ) temp = math. pow (M, mid) if (N % temp = = 0 ): ans = mid start = mid + 1 else : end = mid - 1 return ans # Driver code N = 12 M = 2 print (HighestPower(N, M)) # This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approach using System; class GFG { // Function to find any log(N) base M static int log_a_to_base_b( int a, int b) { return ( int )(Math.Log(a) / Math.Log(b)); } // Function to find the Highest Power // of M which divides N static int HighestPower( int N, int M) { int start = 0, end = log_a_to_base_b(N, M); int ans = 0; while (start <= end) { int mid = start + (end - start) / 2; int temp = ( int )(Math.Pow(M, mid)); if (N % temp == 0) { ans = mid; start = mid + 1; } else { end = mid - 1; } } return ans; } // Driver code public static void Main() { int N = 12; int M = 2; // Function call Console.Write(HighestPower(N, M)); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find any log(N) base M function log_a_to_base_b(a, b) { return Math.log(a) / Math.log(b); } // Function to find the Highest Power // of M which divides N function HighestPower(N, M) { let start = 0, end = log_a_to_base_b(N, M); let ans = 0; while (start <= end) { let mid = start + Math.floor((end - start) / 2); let temp = (Math.pow(M, mid)); if (N % temp == 0) { ans = mid; start = mid + 1; } else { end = mid - 1; } } return ans; } // Driver code let N = 12; let M = 2; document.write(HighestPower(N, M) + '<br>' ); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(log(logM(N)))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!