Divisors of a number
Beginner Problems
Basic Maths
Easy
You are given an integer n. You need to find all the divisors of n. Return all the divisors of n as an array or list in a sorted order.
A number which completely divides another number is called it's divisor.
Examples:
Input: n = 6
Output = [1, 2, 3, 6]
Explanation: The divisors of 6 are 1, 2, 3, 6.
Input: n = 8
Output: [1, 2, 4, 8]
Explanation: The divisors of 8 are 1, 2, 4, 8.
Input: n = 7
Constraints
- 1 <= n <= 1000
Company Tags
TCS
Cognizant
Accenture
Infosys
Capgemini
Wipro
IBM
HCL
Tech Mahindra
MindTree
Editorial
Intuition:
Given a number n, a brute force approach would be to iterate from 1 to n checking each value if it divides n without leaving a remainder. For each divisor found, store it in a list and return the result.
Approach:
- Initialize an array/list to store the divisors.
- Iterate from 1 to n, and check if the current value is a divisor of n or not. Add the value to the array/list if it is a divisor.
- The array/list stores all the divisors of n.
Dry Run:
Solution:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find all
divisors of n */
vector<int> divisors(int n) {
// To store the divisors;
vector<int> ans;
// Iterate from 1 to n
for(int i=1; i <= n; i++) {
// If a divisor is found
if(n % i == 0) {
//Add it to the answer
ans.push_back(i);
}
}
// Return the result
return ans;
}
};
int main()
{
int n = 6;
/* Creating and instance of
Solution class */
Solution sol;
/* Function call to find
all divisors of n */
vector<int> ans = sol.divisors(n);
cout << "The divisors of " << n << " are: ";
for(int i=0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}1234567891011121314151617181920212223242526272829303132333435363738394041424344454647
import java.util.Arrays;
class Solution {
/* Function to find all
divisors of n */
public int[] divisors(int n) {
// Initial size of the array is set to n
int[] temp = new int[n];
int count = 0;
// Iterate from 1 to n
for (int i = 1; i <= n; i++) {
// If a divisor is found
if (n % i == 0) {
// Add it to the array
temp[count++] = i;
}
}
/* Copy the divisors to an
array of the exact size */
int[] ans = Arrays.copyOf(temp, count);
// Return the result
return ans;
}
public static void main(String[] args) {
int n = 6;
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to find
all divisors of n */
int[] ans = sol.divisors(n);
System.out.print("The divisors of " + n + " are: ");
for (int i = 0; i < ans.length; i++) {
System.out.print(ans[i] + " ");
}
}
}
12345678910111213141516171819202122232425262728293031323334
class Solution:
# Function to find all
# divisors of n
def divisors(self, n):
# To store the divisors
ans = []
# Iterate from 1 to n
for i in range(1, n + 1):
# If a divisor is found
if n % i == 0:
# Add it to the answer
ans.append(i)
# Return the result
return ans
# Input number
n = 6
# Creating an instance of
# Solution class
sol = Solution()
# Function call to find
# all divisors of n
ans = sol.divisors(n)
print(f"The divisors of {n} are: ", end="")
for i in range(len(ans)):
print(ans[i], end=" ")
123456789101112131415161718192021222324252627282930313233343536
class Solution {
/* Function to find all
divisors of n */
divisors(n) {
// To store the divisors
let ans = [];
// Iterate from 1 to n
for (let i = 1; i <= n; i++) {
// If a divisor is found
if (n % i === 0) {
// Add it to the answer
ans.push(i);
}
}
// Return the result
return ans;
}
}
// Input number
let n = 6;
/* Creating an instance of
Solution class */
let sol = new Solution();
/* Function call to find
all divisors of n */
let ans = sol.divisors(n);
console.log(`The divisors of ${n} are: `, ans.join(" "));
Complexity Analysis:
Time Complexity: O(N) – Iterating N times, and performing constant time operations in each pass.
Space Complexity: O(sqrt(N)) – A number N can have at max 2*sqrt(N) divisors, which are stored in the array.
Intuition:
The previous approach can be optimized by using the property that for any non-negative integer n, if d is a divisor of n then n/d (known as counterpart divisor) is also a divisor of n.
This property is symmetric about the square root of n by traversing just the first half we can avoid redundant iteration and computations improving the efficiency of the algorithm.
Approach:
- Initialize an array/list to store the divisors.
- Iterate from 1 to sqrt(n), and check if the current value is a divisor of n or not. Add the value to the array/list if it is a divisor. Also, add the counterpart divisor to the array/list if it is different from the current divisor.
- The array/list stores all the divisors of n. Sort the list and return the result.
Dry Run:
Solution:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find all
divisors of n */
vector<int> divisors(int n) {
// To store the divisors;
vector<int> ans;
int sqrtN = sqrt(n);
// Iterate from 1 to sqrtN
for(int i=1; i <= sqrtN; i++) {
// If a divisor is found
if(n % i == 0) {
//Add it to the answer
ans.push_back(i);
/* Add the counterpart divisor
if it's different from i */
if(i != n / i) {
ans.push_back(n/i);
}
}
}
// Sorting the result
sort(ans.begin(), ans.end());
// Return the result
return ans;
}
};
int main()
{
int n = 6;
/* Creating and instance of
Solution class */
Solution sol;
/* Function call to find
all divisors of n */
vector<int> ans = sol.divisors(n);
cout << "The divisors of " << n << " are: ";
for(int i=0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
import java.util.Arrays;
class Solution {
public int[] divisors(int n) {
// To store the divisors
int[] temp = new int[n]; // Temporary array with max possible size
int count = 0;
int sqrtN = (int) Math.sqrt(n);
// Iterate from 1 to sqrtN
for(int i = 1; i <= sqrtN; i++) {
// If a divisor is found
if(n % i == 0) {
// Add it to the answer
temp[count++] = i;
/* Add the counterpart divisor
if it's different from i */
if(i != n / i) {
temp[count++] = n / i;
}
}
}
// Copy only the filled part of temp to the result array
int[] ans = Arrays.copyOf(temp, count);
// Sorting the result
Arrays.sort(ans);
// Return the result
return ans;
}
public static void main(String[] args) {
int n = 6;
// Creating an instance of Solution class
Solution sol = new Solution();
// Function call to find all divisors of n
int[] ans = sol.divisors(n);
System.out.print("The divisors of " + n + " are: ");
for(int i = 0; i < ans.length; i++) {
System.out.print(ans[i] + " ");
}
}
}123456789101112131415161718192021222324252627282930313233343536373839404142
import math
class Solution:
# Function to find all
# divisors of n
def divisors(self, n):
# To store the divisors
ans = []
sqrtN = int(math.sqrt(n))
# Iterate from 1 to sqrtN
for i in range(1, sqrtN + 1):
# If a divisor is found
if n % i == 0:
# Add it to the answer
ans.append(i)
# Add the counterpart divisor
# if it's different from i
if i != n // i:
ans.append(n // i)
# Sorting the result
ans.sort()
# Return the result
return ans
# Creating an instance of
# Solution class
sol = Solution()
n = 6
# Function call to find
# all divisors of n
ans = sol.divisors(n)
print("The divisors of", n, "are:", " ".join(map(str, ans)))123456789101112131415161718192021222324252627282930313233343536373839404142434445
class Solution {
/* Function to find all
divisors of n */
divisors(n) {
// To store the divisors
const ans = [];
const sqrtN = Math.floor(Math.sqrt(n));
// Iterate from 1 to sqrtN
for(let i = 1; i <= sqrtN; i++) {
// If a divisor is found
if(n % i === 0) {
// Add it to the answer
ans.push(i);
/* Add the counterpart divisor
if it's different from i */
if(i !== n / i) {
ans.push(n / i);
}
}
}
// Sorting the result
ans.sort((a, b) => a - b);
// Return the result
return ans;
}
}
// Creating an instance of
// Solution class
const sol = new Solution();
const n = 6;
/* Function call to find
all divisors of n */
const ans = sol.divisors(n);
console.log("The divisors of " + n + " are: " + ans.join(" "));Complexity Analysis:
Time Complexity: O(sqrt(N)) + O(K*Log(K)) – Iterating sqrt(N) times, and performing constant time operations in each pass to get all the divisors in the list. Sorting the list of divisors takes O(K*Log(K)) time where K is the number of divisors of the number.
Space Complexity: O(sqrt(N)) – A number N can have at max 2*sqrt(N) divisors, which are stored in the array.
Notes
Code
✅ Testcase
Input: {'n': '6'}
Expected:
1 2 3 6
1 2 3 6
Actual: -
Time: -
sec
Status: Waiting
Input: {'n': '8'}
Expected:
1 2 4 8
1 2 4 8
Actual: -
Time: -
sec
Status: Waiting
Input: {'n': '7'}
Expected:
1 7
1 7
Actual: -
Time: -
sec
Status: Waiting
Facts
- • Fun Fact: The underlying concept from this problem, finding all the divisors of a number, is surprisingly important in cryptography, a critical part of information security
- • Specifically, it's used in the RSA encryption algorithm, which is widely implemented in communication protocols like HTTPS for secure data transmission over the internet
- • The algorithm uses two large prime numbers, whose product serves as a key
- • The security of RSA is based on the fact that, even knowing the product, it's difficult to determine the original primes (i
- • e
- • , find the divisors), particularly as the prime numbers used become larger