Given a integer N. You have to find all the factors of given number.

First line contains a integer N.

Print all the factors of given number.

Example 1:

Input

12

Output

1 2 3 4 6 12

Example 2:

Input

28

Output

1 2 4 7 14 28

Example 3:

Input

100

Output

1 2 4 5 10 20 25 50 100

Login to see Discussion

Approach 1: Brute Force

Step-i) Initialize an empty string

Step-ii)Run loop from i=1 to i<=number

Step-iii) divide number by i and get the remainder

Step-iv) if remainder is 0 append i to the string

Step-v) return the string

Time Complexity: O(n)

Space Complexity: It can't be said as different numbers have different number of factors

Approach 2: Iterating only upto sqrt on number

Step-i) Create a array list

Step-ii) run loop from i=1 to i<=sqrt of the number

Step-iii) if remainder of number / i is zero add both divisor and quotient to array list

Step-iv)return the array list

Note: here sorting is done to get the output in the increasing order

Time Complexity: O(sqrt(n)) (neglecting the sorting

if sorting is considered it will change to O(nlogn) here n is size of array list

Space Complexity: It can't be said as different numbers have different number of factors

**Note : **

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Login to see Solution