Divine Divisors Problem | C++

January 3, 2022

Divine Divisors Problem

Divine Divisors Problem is one of the easy problems asked in TCS – Codevita. Here is the c++ program to solve the Divine divisor problem where we need to find the divisors of a given number and print them in increasing order. To solve this problem we will use c++ programing language and search for all the divisors of the number and sort them to print them in increasing order. The difficulty level of this problem is low and can be solved easily here is the c++ solution for the problem.

Problem Statement

Print a line containing all the divisors in increasing order separated by space. Include 1 and The number itself.

Input Format: The first line of input contains an integer ‘N’ denoting the number.

Output Format: Print a line containing all the divisors in increasing order separated by space.

Constraints:
1 <= N <= 10^8

S.no	Input	Output
1	10	1 2 5 10

Brute Force Approach

Take all the numbers Possible from 1 to N.
See If N is divisible by the numbers.
If yes, print the numbers, space separated.

Time Complexity : O(N)

The code to implement this:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    if(n%i==0) cout<<i<<" ";
    return 0;
}

Optimised Approach

Take all the numbers Possible from 1 to Square root of N.
See If N is divisible by the numbers.
If yes, store the number, and also N/the number.
Because for every number there will be another number.
Atlast check if the number is perfect square, then you will have included the square root twice.

Time Complexity : O( Sqrt(N) )

The code to implement this:

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	vector<int> v1,v2;
	for(int i=1;i*i<=n;i++) 
	if(n%i==0) 
	{
		v1.push_back(i);
		if(i*i!=n) v2.push_back(n/i);
	}
	for(auto i:v1) cout<<i<<" ";
	reverse(v2.begin(),v2.end());
	for(auto i:v2) cout<<i<<" ";
	return 0;
}

Java

To find the solution of Divine Divisors Problem in Java Programming language click on the button below:

Java

C

To find the solution of Divine Divisors Problem in C Programming language click on the button below:

Python

To find the solution of Divine Divisors Problem in Python Programming language click on the button below:

Python

Divine Divisors Problem | C++