Find all Divisors of a natural number

Easy
0/40
Average time to solve is 15m
profile
Contributed by
9 upvotes

Problem statement

You are given a natural number ‘N’. Find all the divisors of the number ‘N’. Print them in increasing order.

Example: 
Input: ‘N’ = 10 

Output: [1, 2, 5, 10]

1, 2, 5, and 10 are the only divisors of the number 10.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains a natural number ‘N’.
Output format : 
For each test case, you don’t need to print anything just return a sorted array containing all the divisors of ‘N’.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
100
13
Sample Output 1 :
1 2 4 5 10 20 25 50 100
1 13
Explanation Of Sample Input 1 :
For the first case:
100 is divisible by 1 2 4 5 10 20 25 50 100 only.

For the second case:
13 is divisible by 1 and 13 only.
Sample Input 2 :
2
125
15
Sample Output 2 :
1 5 25 125 
1 3 5 15
Hint

Can you think of a way to find the divisors of ‘N’ iteratively?

Approaches (2)
Brute Force

In this approach, We can iterate over all the numbers from 1 to ‘N’ and check if ‘N’ is divisible by that number or not. If it is divisible we can store it in an array. Since we are iterating from 1 to ‘N’ the divisors will be stored in the array in increasing order.

 

The steps are as follows:-

function getAllDivisors( int n ):

  1. Declare an array 'ANS' to store all the divisors of 'N' in increasing order.
  2. Iterate over all the numbers from 1 to 'N', for 'i'=1...'N':
    • If 'N' is divisible by 'i' then push it into the 'ANS' array.
  3. Return the array 'ANS'.
Time Complexity

O( N ), Where ‘N’ is the given natural number. 

 

We are iterating over all the elements from 1 to ‘N’, checking if a number is a divisor of ‘N’ or not takes an O( 1 ) time complexity. So the total time complexity is O( N ).

Hence the time complexity is O( N ).

Space Complexity

O( 1 )

 

We are not using any extra storage space. The array used for storing the answer can be ignored.

Hence space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Find all Divisors of a natural number
Full screen
Console