Factors of a numbers

Palakkgoyal
1 min readDec 13, 2022

Brute force solution:

public class factors{
public static void main(String[] args) {
int n = 20;
findFactors(n);
}
static void findFactors(int n){
for(int i = 1; i <= n; i++){
if(n%i == 0){
System.out.print(i + " ");
}
}
}
}

Time complexity: O(n)

Space complexity: O(1)

Somewhat optimized:

public class factors{
public static void main(String[] args) {
int n = 20;
findFactors(n);
}
static void findFactors(int n){
for(int i = 1; i <= n/2; i++){
if(n%i == 0){
System.out.print(i + " ");
}
}
System.out.print(n + " ");
}
}

Time complexity: O(n)

Space complexity: O(1)

Optimized solution:

public class factors{
public static void main(String[] args) {
int n = 36;
findFactors(n);
}
static void findFactors(int n){
//create a list to store the 2nd half factors
ArrayList<Integer> list = new ArrayList<>();

//run the loop root of n times
for(int i = 1; i*i <= n; i++){
if(n%i == 0){

//if n/i == i it means that it is the root of n so, to avoid repetition of
//root print it just 1 time
if(n/i == i){
System.out.print(i + " ");
}
else{
System.out.print(i + " ");
list.add(n/i);
}
}
}
//print the second half of factors
for(int i = list.size()-1; i >= 0; i--){
System.out.print(list.get(i) + " ");
}

}
}

Time complexity: O(√n)

Space complexity: O(√n)

Thank you for reading. If you have any queries then, please let me know in the comment section. I will surely be responsive toward it.

--

--

Palakkgoyal

Solutions to all your coding related problems at one point. DSA question on daily basis and much more.