712172. All divisors of a Number
Easy
All Divisors of a Number
Summary
Given an integer n, find all divisors (factors) of n. This problem involves basic mathematical concepts like factorization and division.
Detailed Explanation
The idea is to generate all possible factors of the given number. We can do this by iterating from 1 to the square root of n and checking if each number is a divisor of n.
Here's a step-by-step breakdown:
- Initialize an empty list
divisorsto store the divisors. - Iterate from 1 to the square root of
n. - For each iteration, check if the current number is a divisor of
n. If it is:- Add the number and its corresponding quotient (i.e.,
n / current_number) to thedivisorslist.
- Add the number and its corresponding quotient (i.e.,
- Return the
divisorslist.
Here's an example for better understanding:
Suppose we want to find all divisors of 12. We would iterate from 1 to sqrt(12) = 3, and check if each number is a divisor of 12.
- For 1: Yes, 1 is a divisor (quotient = 12).
- For 2: Yes, 2 is a divisor (quotient = 6).
- For 3: No, 3 is not a divisor.
- Since we've reached the square root, we stop here.
The divisors list would be [1, 2, 3, 4, 6, 12].
Time complexity: O(sqrt(n)) Space complexity: O(n)
Optimized Solutions
Java
public List<Integer> allDivisors(int n) {
List<Integer> divisors = new ArrayList<>();
for (int i = 1; i <= Math.sqrt(n); i++) {
if (n % i == 0) {
divisors.add(i);
divisors.add(n / i);
}
}
return divisors;
}