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 Mint log_a_to_base_b(int a, int b){ return log(a) / log(b);}// Function to find the Highest Power// of M which divides Nint 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 codeint 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 Nimport 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 Nimport math# Function to find any log(N) base Mdef log_a_to_base_b(a, b): return math.log(a) / math.log(b)# Function to find the Highest Power# of M which divides Ndef 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 codeN = 12M = 2print(HighestPower(N, M))# This code is contributed by Samim Hossain Mondal. |
C#
// C# program for the above approachusing 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> |
Output
2
Time Complexity: O(log(logM(N)))
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
