Given a number N. You are tasked with finding the smallest number S, such that N is a factor of S! (S factorial). N can be very large.
Examples:
Input : 6 Output : 3 The value of 3! is 6 This is the smallest number which can have 6 as a factor. Input : 997587429953 Output : 998957 If we calculate out 998957!, we shall find that it is divisible by 997587429953. Factors of 997587429953 are 998957 and 998629.
Naive Approach
We iterate from 1 to N, calculating factorial in each case. When we find a factorial that’s capable of having N as a factor, we output it. This method will be difficult to implement for large N, as the factorial can become very large.
Time Complexity: O(N^2)
Optimized Naive Approach
Instead of iterating from 1 to N, we use binary search. This is still a bad method, as we are still trying to calculate N!
Time Complexity O(N log N)
Optimum Solution
We can first calculate all the prime factors of N. We then reduce our problem to finding a factorial which has all the prime factors of N, at least as many times as they appear in N. We then binary search on elements from 1 to N. We can utilize Legendre’s Formula to check whether a number’s factorial has all the same prime factors. We then find the smallest such number.
C++
// Program to find factorial that N belongs to#include <bits/stdc++.h>using namespace std;#define ull unsigned long long// Calculate prime factors for a given numbermap<ull, int> primeFactors(ull num){ // Container for prime factors map<ull, int> ans; // Iterate from 2 to i^2 finding all factors for (ull i = 2; i * i <= num; i++) { while (num % i == 0) { num /= i; ans[i]++; } } // If we still have a remainder // it is also a prime factor if (num > 1) ans[num]++; return ans;}// Calculate occurrence of an element// in factorial of a numberull legendre(ull factor, ull num){ ull count = 0, fac2 = factor; while (num >= factor) { count += num / factor; factor *= fac2; } return count;}bool possible(map<ull, int> &factors, ull num){ // Iterate through prime factors for (map<ull, int>::iterator it = factors.begin(); it != factors.end(); ++it) { // Check if factorial contains less // occurrences of prime factor if (legendre(it->first, num) < it->second) return false; } return true;}// Function to binary search 1 to Null search(ull start, ull end, map<ull, int> &factors){ ull mid = (start + end) / 2; // Prime factors are not in the factorial // Increase the lowerbound if (!possible(factors, mid)) return search(mid + 1, end, factors); // We have reached smallest occurrence if (start == mid) return mid; // Smaller factorial satisfying // requirements may exist, decrease upperbound return search(start, mid, factors);}// Calculate prime factors and searchull findFact(ull num){ map<ull, int> factors = primeFactors(num); return search(1, num, factors);}// Driver functionint main(){ cout << findFact(6) << "n"; cout << findFact(997587429953) << "n"; return 0;} |
Java
// Java Program to find factorial that N belongs toimport java.util.HashMap;import java.util.Iterator;import java.util.Set;class Test{ // Calculate prime factors for a given number static HashMap<Long, Integer> primeFactors(long num) { // Container for prime factors HashMap<Long, Integer> ans = new HashMap<Long, Integer>(){ @Override public Integer get(Object key) { if(containsKey(key)){ return super.get(key); } return 0; } }; // Iterate from 2 to i^2 finding all factors for (long i = 2; i * i <= num; i++) { while (num % i == 0) { num /= i; ans.put(i, ans.get(i)+1); } } // If we still have a remainder // it is also a prime factor if (num > 1) ans.put(num, ans.get(num)+1);; return ans; } // Calculate occurrence of an element // in factorial of a number static long legendre(long factor, long num) { long count = 0, fac2 = factor; while (num >= factor) { count += num / factor; factor *= fac2; } return count; } static boolean possible(HashMap<Long, Integer> factors, long num) { Set<Long> s = factors.keySet(); // Iterate through prime factors Iterator<Long> itr = s.iterator(); while (itr.hasNext()) { long temp = itr.next(); // Check if factorial contains less // occurrences of prime factor if (legendre(temp, num) < factors.get(temp)) return false; } return true; } // Method to binary search 1 to N static long search(long start, long end, HashMap<Long, Integer> factors) { long mid = (start + end) / 2; // Prime factors are not in the factorial // Increase the lowerbound if (!possible(factors, mid)) return search(mid + 1, end, factors); // We have reached smallest occurrence if (start == mid) return mid; // Smaller factorial satisfying // requirements may exist, decrease upperbound return search(start, mid, factors); } // Calculate prime factors and search static long findFact(long num) { HashMap<Long, Integer> factors = primeFactors(num); return search(1, num, factors); } // Driver method public static void main(String args[]) { System.out.println(findFact(6)); System.out.println(findFact(997587429953L)); }}// This code is contributed by Gaurav Miglani |
Python3
# Python Program to find factorial that N belongs to# Calculate prime factors for a given numberdef primeFactors(num): # Container for prime factors ans = dict() i = 2 # Iterate from 2 to i^2 finding all factors while(i * i <= num): while (num % i == 0): num //= i; if i not in ans: ans[i] = 0 ans[i] += 1 # If we still have a remainder # it is also a prime factor if (num > 1): if num not in ans: ans[num] = 0 ans[num] += 1 return ans;# Calculate occurrence of an element# in factorial of a numberdef legendre(factor, num): count = 0 fac2 = factor; while (num >= factor): count += num // factor; factor *= fac2; return count; def possible(factors, num): # Iterate through prime factors for it in factors.keys(): # Check if factorial contains less # occurrences of prime factor if (legendre(it, num) < factors[it]): return False; return True;# Function to binary search 1 to Ndef search(start, end, factors): mid = (start + end) // 2; # Prime factors are not in the factorial # Increase the lowerbound if (not possible(factors, mid)): return search(mid + 1, end, factors); # We have reached smallest occurrence if (start == mid): return mid; # Smaller factorial satisfying # requirements may exist, decrease upperbound return search(start, mid, factors);# Calculate prime factors and searchdef findFact(num): factors = primeFactors(num); return search(1, num, factors);# Driver functionif __name__=='__main__': print(findFact(6)) print(findFact(997587429953)) # This code is contributed by pratham76. |
C#
// C# Program to find factorial that N belongs tousing System;using System.Collections;using System.Collections.Generic;class Test{ // Calculate prime factors for a given number static Dictionary<long, int> primeFactors(long num) { // Container for prime factors Dictionary<long, int> ans = new Dictionary<long, int>(); // Iterate from 2 to i^2 finding all factors for (long i = 2; i * i <= num; i++) { while (num % i == 0) { num /= i; if(!ans.ContainsKey(i)) { ans[i] = 0; } ans[i]++; } } // If we still have a remainder // it is also a prime factor if (num > 1) { if(!ans.ContainsKey(num)) { ans[num] = 0; } ans[num]++; } return ans; } // Calculate occurrence of an element // in factorial of a number static long legendre(long factor, long num) { long count = 0, fac2 = factor; while (num >= factor) { count += num / factor; factor *= fac2; } return count; } static bool possible(Dictionary<long, int> factors, long num) { foreach (int itr in factors.Keys) { // Check if factorial contains less // occurrences of prime factor if (legendre(itr, num) < factors[itr]) return false; } return true; } // Method to binary search 1 to N static long search(long start, long end, Dictionary<long, int> factors) { long mid = (start + end) / 2; // Prime factors are not in the factorial // Increase the lowerbound if (!possible(factors, mid)) return search(mid + 1, end, factors); // We have reached smallest occurrence if (start == mid) return mid; // Smaller factorial satisfying // requirements may exist, decrease upperbound return search(start, mid, factors); } // Calculate prime factors and search static long findFact(long num) { Dictionary<long, int> factors = primeFactors(num); return search(1, num, factors); } // Driver method public static void Main() { Console.WriteLine(findFact(6)); Console.WriteLine(findFact(997587429953L)); }}// This code is contributed by rutvik_56. |
Javascript
// JavaScript Program to find// Smallest number S such that N is a // factor of S factorial or S!// Calculate prime factors for a given numberfunction primeFactors(num){ // Container for prime factors const ans = new Map(); // Iterate from 2 to i^2 finding all factors for (let i = 2; i * i <= num; i++){ while (num % i == 0){ num /= i; if(ans.has(i)){ ans.set(i, ans.get(i) + 1); } else{ ans.set(i,1); } } } // If we still have a remainder // it is also a prime factor if (num > 1){ if(ans.has(num)){ ans.set(num, ans.get(num) + 1); } else{ ans.set(num,1); } } return ans;}// Calculate occurrence of an element// in factorial of a numberfunction legendre(factor,num){ let count = 0; let fac2 = factor; while (num >= factor){ count += Math.floor(num / factor); factor *= fac2; } return count;}function possible(factors,num){ // Iterate through prime factors for (const [key, value] of factors.entries()){ // Check if factorial contains less // occurrences of prime factor if (legendre(key, num) < value){ return false; } } return true;}// Function to binary search 1 to Nfunction search(start,end, factors){ let mid = Math.floor((start + end) / 2); // Prime factors are not in the factorial // Increase the lowerbound if (!possible(factors, mid)){ return search(mid + 1, end, factors); } // We have reached smallest occurrence if (start == mid){ return mid; } // Smaller factorial satisfying // requirements may exist, decrease upperbound return search(start, mid, factors);}// Calculate prime factors and searchfunction findFact(num){ let factors = primeFactors(num); return search(1, num, factors);}// Driver function{ console.log(findFact(6)); console.log(findFact(997587429953)); return 0;}// The code is contributed by Gautam goel (gautamgoel962) |
Output:
3 998957
At no point do we actually calculate a factorial. This means we do not have to worry about the factorial being too large to store.
Lagrange’s Formula runs in O(Log N).
Binary search is O(Log N).
Calculating prime factors is O(sqrt(N))
Iterating through prime factors is O(Log N).
Time complexity becomes: O(sqrt(N) + (Log N)^3)
If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
