Write a Java Program to find the factorial of a given number.
Question Explanation
Finding the factorial of a number is a classic programming challenge that tests your understanding of recursion and iterative solutions. The factorial of a non-negative integer n is the product of all positive integers less than or equal to n, denoted as n!. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. Interviewers often ask this question to assess a candidate's problem-solving skills, ability to implement algorithms, and understanding of mathematical concepts in programming. It's also a common way to evaluate one's knowledge of recursion versus iteration, as both methods can be employed to achieve the same result. Additionally, this question serves as a gateway to discuss more complex topics, such as optimization techniques and handling large numbers. Candidates should be aware of potential pitfalls, such as stack overflow in recursive implementations and performance issues with large inputs. Understanding the factorial function is not only important for interviews but also has real-world applications in fields like combinatorics, probability, and computer science algorithms. Overall, this question encapsulates fundamental programming principles that are crucial for any software engineering role.
Sample Answers
Example 1: Recursive Approach
To find the factorial using a recursive approach, we define a function that calls itself. Here's a simple implementation in Java:
public class Factorial {
public static int factorial(int n) {
if (n == 0) return 1; // Base case
return n * factorial(n - 1); // Recursive call
}
public static void main(String[] args) {
int number = 5;
System.out.println("Factorial of " + number + " is: " + factorial(number));
}
}
In this code:
- We check if
nis 0, returning 1 as the base case. - If not, we multiply
nby the factorial ofn-1.
Complexity Analysis:
- Time Complexity: O(n) because we call the function n times.
- Space Complexity: O(n) due to the call stack from recursion.
This method is straightforward but can lead to stack overflow for large values of n.
Example 2: Iterative Approach
An iterative approach is often more efficient in terms of space usage. Here's how you can implement it in Java:
public class Factorial {
public static int factorial(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i; // Multiply the result by i
}
return result;
}
public static void main(String[] args) {
int number = 5;
System.out.println("Factorial of " + number + " is: " + factorial(number));
}
}
In this implementation:
- We use a
forloop to iterate from 1 to n, multiplying each value to the result.
Complexity Analysis:
- Time Complexity: O(n) as we loop through n.
- Space Complexity: O(1) since we only use a constant amount of space.
This method is preferred for larger inputs due to its efficiency.
Example 3: Handling Large Numbers with BigInteger
When calculating the factorial of large numbers, using Java's BigInteger class is essential to avoid integer overflow. Here's how you can implement it:
import java.math.BigInteger;
public class Factorial {
public static BigInteger factorial(int n) {
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
public static void main(String[] args) {
int number = 20;
System.out.println("Factorial of " + number + " is: " + factorial(number));
}
}
In this code:
- We use
BigIntegerto handle very large numbers that exceed standard data types.
Complexity Analysis:
- Time Complexity: O(n) due to the loop.
- Space Complexity: O(1) for the storage of the result.
This approach is crucial for applications in combinatorics or probability that require factorials of large numbers.
Keywords
Ready to practice more questions?
Explore our collection of technical interview questions from top companies.
View All Questions