Given two integers 
and 
. The task is to find the maximum value of x, such that, n! % (k^x) = 0.
Examples:
Input : n = 5, k = 2 Output : 3 Explanation : Given n = 5 and k = 2. So, n! = 120. Now for different values of x: n! % 2^0 = 0, n! % 2^1 = 0, n! % 2^2 = 0, n! % 2^3 = 0, n! % 2^4 = 8, n! % 2^5 = 24, n! % 2^6 = 56, n! % 2^7 = 120. So, the answer should be 3. Input : n = 1000, x = 2 Output : 994
Approach:
- First take the squareroot of
and store it in a variable say, 
. - Run the loop from i=2 to m.
- If i = m then copy k to i.
- If k is divisible by i then divide k by i.
- Run a loop to n and add the quotient to a variable say,
. - Store the minimum value of r after every loop.
.
.Below is the implementation of the above approach:
C++
// C++ program to maximize the value // of x such that n! % (k^x) = 0 #include<iostream>#include<math.h>using namespace std;class GfG{ // Function to maximize the value // of x such that n! % (k^x) = 0 public: int findX(int n, int k) { int r = n, v, u; // Find square root of k and add 1 to it int m = sqrt(k) + 1; // Run the loop from 2 to m and k // should be greater than 1 for (int i = 2; i <= m && k > 1; i++) { if (i == m) { i = k; } // optimize the value of k for (u = v = 0; k % i == 0; v++) { k /= i; } if (v > 0) { int t = n; while (t > 0) { t /= i; u += t; } // Minimum store r = min(r, u / v); } } return r; } }; // Driver Code int main() { GfG g; int n = 5; int k = 2; cout<<g.findX(n, k); } //This code is contributed by Soumik |
Java
// Java program to maximize the value// of x such that n! % (k^x) = 0import java.util.*;public class GfG { // Function to maximize the value // of x such that n! % (k^x) = 0 private static int findX(int n, int k) { int r = n, v, u; // Find square root of k and add 1 to it int m = (int)Math.sqrt(k) + 1; // Run the loop from 2 to m and k // should be greater than 1 for (int i = 2; i <= m && k > 1; i++) { if (i == m) { i = k; } // optimize the value of k for (u = v = 0; k % i == 0; v++) { k /= i; } if (v > 0) { int t = n; while (t > 0) { t /= i; u += t; } // Minimum store r = Math.min(r, u / v); } } return r; } // Driver Code public static void main(String args[]) { int n = 5; int k = 2; System.out.println(findX(n, k)); }} |
Python 3
# Python 3 program to maximize the value# of x such that n! % (k^x) = 0import math# Function to maximize the value# of x such that n! % (k^x) = 0def findX(n, k): r = n # Find square root of k # and add 1 to it m = int(math.sqrt(k)) + 1 # Run the loop from 2 to m # and k should be greater than 1 i = 2 while i <= m and k > 1 : if (i == m) : i = k # optimize the value of k u = 0 v = 0 while k % i == 0 : k //= i v += 1 if (v > 0) : t = n while (t > 0) : t //= i u += t # Minimum store r = min(r, u // v) i += 1 return r# Driver Codeif __name__ == "__main__": n = 5 k = 2 print(findX(n, k))# This code is contributed# by ChitraNayal |
C#
// C# program to maximize the value // of x such that n! % (k^x) = 0 using System;class GfG{ // Function to maximize the value // of x such that n! % (k^x) = 0 public int findX(int n, int k) { int r = n, v, u; // Find square root of k and add 1 to it int m = (int)Math.Sqrt(k) + 1; // Run the loop from 2 to m and k // should be greater than 1 for (int i = 2; i <= m && k > 1; i++) { if (i == m) { i = k; } // optimize the value of k for (u = v = 0; k % i == 0; v++) { k /= i; } if (v > 0) { int t = n; while (t > 0) { t /= i; u += t; } // Minimum store r = Math.Min(r, u / v); } } return r; } } // Driver Code class geek{ public static void Main() { GfG g = new GfG(); int n = 5; int k = 2; Console.WriteLine(g.findX(n, k)); } } |
PHP
<?php// PHP program to maximize the value // of x such that n! % (k^x) = 0 // Function to maximize the value // of x such that n! % (k^x) = 0 function findX($n, $k) { $r = $n; // Find square root of k and add 1 to it $m = (int)sqrt($k) + 1; // Run the loop from 2 to m and k // should be greater than 1 for ($i = 2; $i <= $m && $k > 1; $i++) { if ($i == $m) { $i = $k; } // optimize the value of k for ($u = $v = 0; $k % $i == 0; $v++) { $k = (int)($k / $i); } if ($v > 0) { $t = $n; while ($t > 0) { $t = (int)($t / $i); $u = $u + $t; } // Minimum store $r = min($r, (int)($u / $v)); } } return $r; } // Driver Code $n = 5; $k = 2; echo findX($n, $k); // This code is contributed by// Archana_kumari?> |
Javascript
<script> // Javascript program to maximize the value // of x such that n! % (k^x) = 0 // Function to maximize the value // of x such that n! % (k^x) = 0 function findX(n, k) { let r = n; let v = 0; let u = 0; // Find square root of k and add 1 to it let m = Math.floor(Math.sqrt(k) + 1); // Run the loop from 2 to m and k // should be greater than 1 for (let i = 2; i <= m && k > 1; i++) { if (i == m) { i = k; } // optimize the value of k for (let u = v = 0; k % i == 0; v++) { k = Math.floor(k / i); } if (v > 0) { let t = n; while (t > 0) { t = Math.floor(t / i); u += t; } // Minimum store r = Math.min(r, Math.floor(u / v)); } } return r; } // Driver Code let n = 5; let k = 2; document.write(findX(n, k)); //This code is contributed by gfgking</script> |
Output:
3
Time complexity: O(sqrt(k)log(n)), where n is the input parameter n and k is the input parameter k.
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!
