हिन्दी flagहिन्दी  
CLOSE

Suggested:

Digits

HomeLearnDatastructure in cpp languageBasic Maths Digits

Digits

1️⃣ Extracting Digits of a Number

To extract digits from a number, you can use modulus and division operations.

To extract digits from a number, you can use a loop that repeatedly divides the number by 10. In each iteration, you take the remainder when dividing by 10, which gives you the last digit. Then, you divide the number by 10 to remove that digit.

Example: Extracting Digits from a Number

Let's consider the number 12345. We'll extract each digit one by one.

1 Initialize the number

int n = 12345;

2 Loop to Extract Digits

We use a loop to extract each digit.

while (n > 0) {
    int digit = n % 10;  // Extract the last digit
    std::cout << "Extracted Digit: " << digit << std::endl;
    n = n / 10;  // Remove the last digit from the number
}

Explanation of the Code:

  • Step 1: Initialize the number: The variable n is initialized with the value 12345.
  • Step 2: Loop to extract digits:
    • Iteration 1:
      • digit = 12345 % 10 → digit = 5 (The last digit is extracted).
      • n = 12345 / 10 → n = 1234 (The last digit is removed).
    • Iteration 2:
      • digit = 1234 % 10 → digit = 4 (The new last digit is extracted).
      • n = 1234 / 10 → n = 123 (The last digit is removed).
    • Iteration 3:
      • digit = 123 % 10 → digit = 3.
      • n = 123 / 10 → n = 12.
    • Iteration 4:
      • digit = 12 % 10 → digit = 2.
      • n = 12 / 10 → n = 1.
    • Iteration 5:
      • digit = 1 % 10 → digit = 1.
      • n = 1 / 10 → n = 0.
    • The loop terminates when n becomes 0.

Each digit (5, 4, 3, 2, 1) is extracted and printed. These digits correspond to the original number but are extracted from right to left (from least significant to most significant digit).

Output:

Extracted Digit: 5
Extracted Digit: 4
Extracted Digit: 3
Extracted Digit: 2
Extracted Digit: 1

2️⃣ Counting Digits in a Number

To find the number of digits in a given integer n, you can use a simple loop, logarithmic approach, or convert the number to a string.

Using Loop:

int countDigits(int n) {

	if (n == 0) return 1;

    int count = 0;
    while (n != 0) {
        n /= 10;  // Remove the last digit
        count++;  // Increment the digit count
    }
    return count;
}

Code Explanation:

  • Initialize a counter to 0.
  • While the number is not 0:
    • Increment the counter.
    • Divide the number by 10 (this removes the last digit).
  • The counter now holds the number of digits.

Example:

Let's count the digits in n = 12345.

  • Start with n = 12345 and count = 0.
  • Divide 12345 by 10, resulting in 1234. Increment count to 1.
  • Divide 1234 by 10, resulting in 123. Increment count to 2.
  • Divide 123 by 10, resulting in 12. Increment count to 3.
  • Divide 12 by 10, resulting in 1. Increment count to 4.
  • Divide 1 by 10, resulting in 0. Increment count to 5.

Now n = 0, so the loop stops, and the count is 5.

Complexity Analysis:

  • Time Complexity: The time complexity is O(log n) due to the division by 10 in each iteration of the while loop.
  • Space Complexity: The space complexity is O(1) since only a constant amount of space is used for the count variable.

Using Logarithmic:

This method leverages the properties of logarithms. Specifically, the number of digits in a positive integer n is given by floor(log10(n)) + 1.

#include <cmath>

int countDigits(int n) {
    return n == 0 ? 1 : (int)log10(n) + 1;
}

// OR

#include <cmath>

int countDigits(int n) {
    if (n == 0) return 1;  // Special case for 0
    return floor(log10(n) + 1);
}
  • If the number is 0, it has exactly 1 digit.
  • Otherwise, compute log10(n), take the floor of that value, and add 1.

Example:

For n = 12345:

  • log10(12345) is approximately 4.0915149772.
  • Taking the floor gives 4.
  • Adding 1 gives 5.

Using String Conversion

This method is the most straightforward but might not be as efficient as the others, especially for very large numbers. Convert the number to a string, and then count the number of characters in that string.

#include <string>

int countDigits(int n) {
    std::string numStr = std::to_string(n);
    return numStr.length();
}
  1. Convert the integer to a string.
  2. Return the length of the string.

Example: For n = 12345:

  • Convert 12345 to the string "12345".
  • The length of "12345" is 5.

3️⃣ Reversing Digits of a Number

The goal is to transform a number like 1234 into 4321. This can be achieved using simple arithmetic operations and is useful in various scenarios, such as checking for palindromic numbers or manipulating numerical data.

Example:

Input: n = 25

Output: 52

Explanation: Reverse of 25 is 52.
Input: n = 123

Output: 321

Explanation: Reverse of 123 is 321.

Constraints:

Constraints:
0 <= n <= 5000
n will contain no leading zeroes except when it is 0 itself.

Intuition:

Given a number, it can be reversed if all the digits are extracted from the end of the original number and pushed at the back of a new reversed number.

Approach:

  1. Initialize a reversed number with zero, which will store the reversed number. To push any digit at the end of the reversed number, the following mathematical operation can be used:
    revNum = (revNum * 10) + digit.
  2. The last digit of the original number can be found by using the modulus operator (used to find the remainder for any division) with the number 10.
  3. Iterate on the original number till there are digits left. In every iteration, extract the last (rightmost) digit and push it at the back of the reversed number. Also, divide the original number by 10 so that the remaining digits can be extracted in the next iterations.
  4. Once the iterations are over, the reversed number will be stored in the reverse of the original number.

Steps to Reverse Digits of a Number

  1. Initialize Variables:
    • Start with two variables: one to store the reversed number (reversed) and another to hold the original number (n).
  2. Extract Digits:
    • Use the modulus operator % to get the last digit of the number.
    • Update the reversed number by shifting its digits to the left and adding the new digit.
  3. Update the Number:
    • Remove the last digit from the original number by performing integer division / by 10.
  4. Repeat:
    • Continue the process until the original number is reduced to zero.
  5. Output:
    • The reversed number is stored in the reversed variable.

Dry Run:

Initially
N = 123
reverseNumber = 0

First Iteration:

lastDigit = N%10 = 123%10 = 3
reverseNumbe = reverseNumber*10 + lastDigit = 0*10+3 = 3
N = N/10 = 123/10 = 12

Second Iteration:

lastDigit = N%10 = 12%10 = 2
reverseNumber = reverseNumber*10 + lastDigit = 3*10+2 = 32
N = N/10 = 12/10 = 1

Third Iteration:

lastDigit = N%10 = 1%10 = 1
reverseNumber = reverseNumber*10 + lastDigit = 32*10+1 = 321
N = N/10 = 1/10 = 0
N = 0
reverseNumber = 321

Since N = 0, the loop has terminated, and function returned reverseNumber

Code:

#include <iostream>

int reverseNumber(int n) {
    int reversed = 0; // This will hold the reversed number
    while (n != 0) {
        int digit = n % 10; // Extract the last digit
        reversed = reversed * 10 + digit; // Append the digit to the reversed number
        n /= 10; // Remove the last digit from the original number
    }
    return reversed;
}

int main() {
    int number = 1234;
    int reversedNumber = reverseNumber(number);

    std::cout << "Original Number: " << number << std::endl;
    std::cout << "Reversed Number: " << reversedNumber << std::endl;

    return 0;
}

Explanation

  1. Initialization:
    • reversed is initialized to 0. This will eventually hold the reversed number.
    • n is the original number, which will be modified to extract digits.
  2. Extracting and Reversing:
    • digit = n % 10 extracts the last digit of n. For 1234, this will first be 4, then 3, then 2, and finally 1.
    • reversed = reversed * 10 + digit adds the extracted digit to the reversed number. Initially, reversed is 0, so reversed = 0 * 10 + 4 becomes 4. In the next iteration, reversed = 4 * 10 + 3 becomes 43, and so on.
  3. Updating the Number:
    • n /= 10 removes the last digit from n. After processing the last digit 4, n becomes 123, then 12, then 1, and finally 0.
  4. Termination:
    • The loop continues until n becomes 0. At this point, all digits have been processed, and reversed contains the digits in reverse order.
  5. Output:
    • The final result is printed, showing the reversed number.

Example Walkthrough

Let's walk through an example with the number 1234:

  1. First Iteration:
    • digit = 1234 % 10 = 4
    • reversed = 0 * 10 + 4 = 4
    • n = 1234 / 10 = 123
  2. Second Iteration:
    • digit = 123 % 10 = 3
    • reversed = 4 * 10 + 3 = 43
    • n = 123 / 10 = 12
  3. Third Iteration:
    • digit = 12 % 10 = 2
    • reversed = 43 * 10 + 2 = 432
    • n = 12 / 10 = 1
  4. Fourth Iteration:
    • digit = 1 % 10 = 1
    • reversed = 432 * 10 + 1 = 4321
    • n = 1 / 10 = 0
  5. Exit Loop:
    • n is 0, so the loop terminates. The final reversed number is 4321.

Complexity Analysis:

  • Time Complexity: O(log10(N)) – In every iteration, N is divided by 10 (equivalent to the number of digits in N.)
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

4️⃣ Checking for Palindromic Numbers

A palindrome number is a number which reads the same both left to right and right to left

A palindromic number is one that reads the same forwards and backwards. Checking if a number is palindromic involves comparing the number to its reverse and verifying if they are the same.

Example:

Input: n = 121

Output: true

Explanation: When read from left to right : 121.

When read from right to left : 121.
Input: n = 123

Output: false

Explanation: When read from left to right : 123.

When read from right to left : 321.

Constraints:

0 <= n <= 5000
n will contain no leading zeroes except when it is 0 itself.

Intuition:

Given a number, it is a palindrome if it remains the same when its digits are reversed.

Approach:

  1. Initialize a reversed number with zero, which will store the reversed number. Store a copy of the original number which can be used to compare the original number and reversed number.
  2. To push any digit at the end of the reversed number, the following mathematical operation can be used: revNum = (revNum * 10) + digit.
  3. The last digit of the original number can be found by using the modulus operator (used to find the remainder for any division) with the number 10.
  4. Iterate on the original number till there are digits left. In every iteration, extract the last (rightmost) digit and push it at the back of the reversed number. Also, divide the original number by 10 so that the remaining digits can be extracted in the next iterations.
  5. Once the iterations are over, the reversed number will be stored in the reverse of the original number. Check if the stored copy of the original number is the same as the reversed number. If yes, the number is palindrome else it is not a palindrome.

Dry Run:

Initially

N = 121
copy = 121
reverseNumber = 0

First Iteration:

lastDigit = N%10 = 121%10 = 1
reverseNumber = reverseNumber * 10 + lastDigit = 0*10+1 = 1
N = N/10 = 121/10 = 12

Second Iteration

lastDigit = N%10 = 12%10 = 2
reverseNumber = reverseNumber * 10 + lastDigit = 1*10+2 = 12
N = N/10 = 12/10 = 1

Third Iteration

lastDigit = N%10 = 1%10 = 1
reverseNumber = reverseNumber * 10 + lastDigit = 12*10+1 = 121
N = N/10 = 1/10 = 0
N = 0
copy = 121
reverseNumber = 121

Since N = 0, the loop has been terminated
Returns true since copy and reverseNumber both are same.

Steps to Check if a Number is Palindromic

  1. Reverse the Number: Create a reversed version of the number by extracting its digits and reassembling them in reverse order.
  2. Compare the Original and Reversed Numbers: If the reversed number is equal to the original number, then the number is palindromic.

Example and Code Explanation

Let's walk through an example and the corresponding code to check if a number is palindromic.

Example

Consider the number 1221:

  1. Reverse the Number:
    • Original number: 1221
    • Reversed number: 1221
  2. Comparison:
    • Original number: 1221
    • Reversed number: 1221
    • Since both numbers are equal, 1221 is a palindromic number.

Here’s a detailed code example in C++ that checks if a number is palindromic:

#include <iostream>

// Function to reverse a number
int reverseNumber(int n) {
    int reversed = 0;
    while (n != 0) {
        int digit = n % 10;        // Get the last digit
        reversed = reversed * 10 + digit; // Append it to reversed
        n /= 10;                   // Remove the last digit
    }
    return reversed;
}

// Function to check if a number is palindromic
bool isPalindrome(int n) {
    if (n < 0) return false; // Negative numbers are not palindromic

    int reversed = reverseNumber(n); // Get the reversed number
    return n == reversed; // Check if original and reversed numbers are the same
}

int main() {
    int number = 1221; // Example number
    if (isPalindrome(number)) {
        std::cout << number << " is a palindromic number." << std::endl;
    } else {
        std::cout << number << " is not a palindromic number." << std::endl;
    }
    return 0;
}

Code Breakdown

  1. Reverse the Number (reverseNumber function):
    • Initialize reversed to 0.
    • While n is not 0, repeatedly extract the last digit of n using n % 10.
    • Append the extracted digit to the reversed variable and remove the last digit from n using integer division (n /= 10).
  2. Check Palindromic (isPalindrome function):
    • Handle edge cases like negative numbers, which are not considered palindromic.
    • Call reverseNumber to get the reversed version of n.
    • Compare the original number with the reversed number. If they are equal, return true; otherwise, return false.
  3. Main Function:
    • Test the isPalindrome function with an example number (1221 in this case) and print whether the number is palindromic or not.

Considerations

  • Negative Numbers: Negative numbers are generally not considered palindromic because the minus sign would be in the reversed position.
  • Single-Digit Numbers: Any single-digit number (0-9) is inherently a palindrome.

Complexity Analysis:

  • Time Complexity: O(log10(N)) – In every iteration, N is divided by 10 (equivalent to the number of digits in N.)
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

5️⃣ Count numbers of odd digits in a number

You are given an integer n. You need to return the number of odd digits present in the number.

The number will have no leading zeroes, except when the number is 0 itself.

Example:

Input: n = 5

Output: 1

Explanation: 5 is an odd digit.
Input: n = 25

Output: 1

Explanation: The only odd digit in 25 is 5.
Constraints:
0 <= n <= 5000
n will contain no leading zeroes except when it is 0 itself.

Intuition:

Given a number, all the digits in the number can be extracted one by one from right to left which can be checked for even and odd.

Approach:

  • The last digit of the given number can be found by using the modulus operator (used to find the remainder for any division) with the number 10.
  • Iterate on the original number till there are digits left, extract the last (rightmost) digit, and check whether the digit is odd or not. In every iteration, divide the original number by 10 so that the remaining digits can be extracted in the next iterations.
  • Keep a counter to count the number of odd digits found in the number and every time an odd digit is encountered, increment the counter.

Dry Run:

Initially N = 123
oddDigits = 0

First Iteration

lastDigit = N % 10 = 123 % 10 = 3 -> odd
N = N / 10 = 123/10 = 12
oddDigits = oddDigits + 1 = 0+1 = 1

Second Iteration

lastDigit = N % 10 = 12 % 10 = 2 -> even
N = N / 10 = 12/10 = 1
oddDigits = 1 -> no change

Third Iteration

lastDigit = N % 10 = 1 % 10 = 1 -> odd
N = N / 10 = 1/10 = 0
oddDigits = oddDigits + 1 = 1+1 = 2
N = 0
oddDigits = 2
Since N=0 hence the loop terminated and returned oddDigits to caller function

Code:

/* Function to count number
    of odd digits in N */
    int countOddDigit(int n) {
        /* Counter to store the 
        number of odd digits */
        int oddDigits = 0;

        // Iterate till there are digits left
        while (n > 0) {
            // Extract last digit
            int lastDigit = n % 10;
            
            // Check if digit is odd
            if (lastDigit % 2 != 0) {
                // Increment counter
                oddDigits = oddDigits + 1;
            }
            n = n / 10;
        }

        return oddDigits;
    }

Complexity Analysis:

  • Time Complexity: The time complexity is O(log n) as the while loop iterates through each digit of n.
  • Space Complexity: The space complexity is O(1) since only a fixed amount of extra space is used regardless of the input size.

6️⃣ Return the largest digit in a number

You are given an integer n. Return the largest digit present in the number.

Example:

Example 1
Input: n = 25

Output: 5

Explanation: The largest digit in 25 is 5.
Example 2
Input: n = 99

Output: 9

Explanation: The largest digit in 99 is 9.

Constraints:

0 <= n <= 5000
n will contain no leading zeroes except when it is 0 itself.

Intuition:

Given a number, all the digits can be extracted from the back (right) successively and the maximum of all the digits can be found by comparing every digit.

Approach:

  1. Initialize a variable largest digit with zero that will store the largest digit in the given number.
  2. The last digit of the original number can be found by using the modulus operator (used to find the remainder for any division) with the number 10.
  3. Iterate on the original number till there are digits left. In every iteration, extract the last (rightmost) digit and check if it is greater than the largest digit. If found greater, update the largest digit with the current digit.
  4. Once the iterations are over, the largest digit in the given number is returned as answer.

Dry Run:

Initially
N = 198
largestDigit = 0

First Iteration

lastDigit = N%10 = 198%10 = 8
largestDigit = 8, since lastDigit > largestDigit
N = N / 10 = 198/10 = 19

largestDigit is updated since 8 > 0

Second Iteration

lastDigit = N%10 = 19%10 = 9
largestDigit = 9, since lastDigit > largestDigit
N = N / 10 = 19/10 = 1

largestDigit is updated since 9 > 8

Third Iteration

lastDigit = N%10 = 1%10 = 1
largestDigit = 9, unchanged
N = N / 10 = 1/10 = 0

largestDigit remain unchanged since 1 < 9
N = 0
largestDigit = 9

Since N = 0, the loop has been terminated
Return largestDigit

Code:

int largestDigit(int n) {
        // Variable to store the largest digit
        int largestDigit = 0;

        /* Keep on iterating while there
        are digits left to extract */
        while(n > 0) {
            int lastDigit = n % 10;

            /* If the current digit is greater than 
            largest digit, update largest digit */
            if(lastDigit > largestDigit) {
                largestDigit = lastDigit;
            }
            
            n = n / 10;
        }
        
        // Return the largest digit 
        return largestDigit;
    }

Complexity Analysis:

  • Time Complexity: O(log10(N)) – In every iteration, N is divided by 10 (equivalent to the number of digits in N.)
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

7️⃣ Factorial of a given number

You are given an integer n. Return the value of n! or n factorial.

Factorial of a number is the product of all positive integers less than or equal to that number.

Examples:

Example 1
Input: n = 2

Output: 2

Explanation: 2! = 1 * 2 = 2.
Example 2
Input: n = 0

Output: 1

Explanation: 0! is defined as 1.

Constraints

0 <= n <= 10

Intuition:

Given a number, its factorial can be found by multiplying all positive integers starting from 1 to the given number.

Approach:

  1. Initialize a variable with 1 that will store the factorial of the given number.
  2. Start iterating from 1 to the given number, and in every pass multiply the variable with the current number.
  3. After the iterations are completed, the variable storing the answer can be returned.

Dry Run:

Initially
N = 5
fact = 1
fact = fact*i = 1*1 = 1
fact = fact*i = 1*2 = 2
fact = fact*i = 2*3 = 6
fact = fact*i = 6*4 = 24
fact = fact*i = 24*5 = 120

Code:

int factorial(int n) {
        // Variable to store the factorial
        int fact = 1;

        // Iterate from 1 to n
        for(int i = 1; i <= n; i++) {
            // Multiply fact with current number
            fact = fact * i;
        }
        
        // Return the factorial stored
        return fact;
    }

Complexity Analysis:

  • Time Complexity: O(N) – Iterating once from 1 to N.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

8️⃣ Check if the number if armstrong

You are given an integer n. You need to check whether it is an armstrong number or not. Return true if it is an armstrong number, otherwise return false.

An armstrong number is a number which is equal to the sum of the digits of the number, raised to the power of the number of digits.

Examples:

Example 1
Input: n = 153

Output: true

Explanation: Number of digits : 3.

1 ^ 3 + 5 ^ 3 + 3 ^ 3 = 1 + 125 + 27 = 153.

Therefore, it is an Armstrong number.
Example 2
Input: n = 12

Output: false

Explanation: Number of digits : 2.

1 ^ 2 + 2 ^ 2 = 1 + 4 = 5.

Therefore, it is not an Armstrong number.

Constraints

0 <= n <= 5000

Intuition:

Given a number, the number of digits can be found. Once the number of digits is known, all the digits can be extracted one by one from the right which can be used to check whether the number is Armstrong or not.

Approach:

  1. Initialize three variables:
    1. count - to store the count of digits in the given number.
    2. sum - to store the sum of the digits of the number raised to the power of the number of digits.
    3. copy - to store the copy of the original number.
  2. Start iterating on the given number till there are digits left to extract. In each iteration, extract the last digit (using the modulus operator with 10), and add the digit raised to the power of count to sum. Update n by integer division with 10 effectively removing the last digit.
  3. After the iterations are over, check if the copy of the original is the same as the sum stored. If found equal, the original number is an Armstrong number, else it is not.

Dry Run:

N = 153
copy = 153
count of digits in N -> count = 3
sum = 0

First Iteration

lastDigit = N%10 = 153%10 = 3
sum = sum + lastDigit^count = 0 + 3^3 = 27
N = N/10 = 153/10 = 15

Second Iteration

lastDigit = N%10 = 15%10 = 5
sum = sum + lastDigit^count = 27 + 5^3 = 152
N = N/10 = 15/10 = 1

Third Iteration

lastDigit = N%10 = 1%10 = 1
sum = sum + lastDigit^count = 152 + 1^3 = 153
N = N/10 = 1/10 = 0
N = 0
copy = 153
sum = 153

Since N = 0, the loop is terminated
Return true since copy is equal to sum

Code

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

class Solution {
private:
    /* Function to count the 
    number of digits in N */
    int countDigit(int n) {
        int count = log10(n) + 1;
        return count;
    }
    
public:
    /* Function to find whether the
    number is Armstrong or not */
    bool isArmstrong(int n) {
        
        // Store the count of digits
        int count = countDigit(n);
        
        // Variable to store the sum
        int sum = 0;
        
        // Variable to store the copy
        int copy = n;
        
        /* Iterate through each
        digit of the number */
        while(n > 0){
            
            // Extract the last digit
            int lastDigit = n % 10;
            
            // Update sum
            sum += pow(lastDigit, count); 
            
            /* Remove the last digit
             from the number */
            n = n / 10;
        }
        
        /* Check if the sum of digits raised to the
        power of k equals the original number */
        if(sum == copy) return true;
        return false;
    }
};

int main() {
    int n = 153;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
     given number is Armstrong or not */
    bool ans = sol.isArmstrong(n);
    
    if(ans) {
        cout << n << " is an Armstrong number." << endl;
    } else {
        cout << n << " is not an Armstrong number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(log10(N)) – N is being divided by 10 until it becomes zero resulting in log10(N) iterations and in each iteration constant time operations are performed.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space, regardless of the size of the input.

9️⃣ Check for perfect number

You are given an integer n. You need to check if the number is a perfect number or not. Return true is it is a perfect number, otherwise return false.

A perfect number is a number whose proper divisors add up to the number itself.

Example:

Example 1
Input: n = 6

Output: true

Explanation: Proper divisors of 6 are 1, 2, 3.

1 + 2 + 3 = 6.
Example 2
Input: n = 4

Output: false

Explanation: Proper divisors of 4 are 1, 2.

1 + 2 = 3.

Constraints:

1 <= n <= 5000

Brute Force Approach

Intuition:

Given a number, all its proper divisors (divisors that divide the number without leaving any remainder, excluding the number itself) can be found and summed up. Then, the sum can be compared with the number itself. If the sum is the same as the number, then it is a perfect number, otherwise, it is not.

Approach:

  1. Initialize a variable with 0 to store the sum of the proper divisors.
  2. Start iterating from 1 to the given number(excluding) using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable.
  3. If it is divisible completely, the current value of the loop variable is a proper divisor which is added to the sum storing sum of proper divisors.
  4. After the sum is calculated, compare it with the given number. If found equal, the given number is perfect, otherwise, it is not.

Dry Run:

Initially
Initially
N = 6
sum = 0
First Pass
i = 1
sum = sum + i = 0 + 1 = 1
6 is divisible by 1
Second Pass
i = 2
sum = sum + i = 1 + 2 = 3
6 is divisible by 2
Third Pass
i = 3
sum = sum + i = 3 + 3 = 6
6 is divisible by 3
Fourth Pass
i = 4
sum = 6
6 is not divisible by 4
Fifth Pass
i = 5
sum = 6
6 is not divisible by 5
Since  i = N, the loop has been terminated,
sum = N = 6
Return true since sum is equal to N.

Code

bool isPerfect(int n) {
        
        /* Variable to store the sum
        of all proper divisors */
        int sum = 0;
        
        // Loop from 1 to n
        for(int i=1; i < n; ++i) {
            
            // Check if i is a proper divisor
            if(n % i == 0){
                // Update sum
                sum = sum + i;
            }
        }
        
        // Compare sum and n
        if(sum == n) return true;
        return false;
    }

Complexity Analysis:

  • Time Complexity: O(N) – Running a loop from 1 to N.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space, regardless of the size of input.

Optimal Approach

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 is also a divisor (counterpart divisor) of n. This property is symmetric about the square root of n. By traversing just the first half, the redundant iterations and computations can be avoided improving the efficiency of the algorithm.

Approach:

  1. Initialize a variable with 0 to store the sum of the proper divisors.
  2. Start iterating from 1 to square root of the given number using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable.
  3. If it is divisible completely, the current value of the loop variable is a proper divisor which is added to the sum storing sum of proper divisors. Also, using the property discussed above, another proper divisor can be found.
  4. Note: Before adding the counterpart divisor, it should be checked if both the proper divisors are different and the counterpart divisor is not the number itself. If they are different and the counterpart divisor is not the number itself, the counterpart divisor should be added to the sum. Otherwise, the counterpart divisor should not be added to the sum ensuring that the divisor is not added twice.
  5. After the sum is calculated, compare it with the given number. If found equal, the given number is perfect, otherwise, it is not.

Edge Case:

When the given number is 1, there are no proper divisors of 1, i.e., the sum of proper divisors of the number is 0. Hence, 1 is not a perfect number.

Code:

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

class Solution {
public:
    /* Function to find whether the
    number is perfect or not */
    bool isPerfect(int n) {
        // Edge case
        if(n == 1) return false;
        
        /* Variable to store the sum
        of all proper divisors */
        int sum = 0;
        
        // Loop from 1 to square root of n
        for(int i=1; i <= sqrt(n); ++i) {
            
            // Check if i is a proper divisor
            if(n % i == 0){
                // Update sum
                sum = sum + i;
                
                /* Add the counterpart divisor
                if it's different from i and
                if it is not n itself */
                if(n/i != n && i != n/i) {
                    sum = sum + (n/i);
                }
            }
        }
        
        // Compare sum and n
        if(sum == n) return true;
        return false;
    }
};

int main() {
    int n = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
     given number is perfect or not */
    bool ans = sol.isPerfect(n);
    
    if(ans) {
        cout << n << " is a perfect number." << endl;
    } else {
        cout << n << " is not a perfect number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(sqrt(N)) – Running a loop from 1 to square root of N.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space, regardless of the size of input.

1️⃣0️⃣ Check for prime number

You are given an integer n. You need to check if the number is prime or not. Return true if it is a prime number, otherwise return false.

A prime number is a number which has no divisors except 1 and itself.

Examples:

Example 1
Input: n = 5

Output: true

Explanation: The only divisors of 5 are 1 and 5 , So the number 5 is prime.
Example 2
Input: n = 8

Output: false

Explanation: The divisors of 8 are 1, 2, 4, 8, thus it is not a prime number.

Constraints:

2 <= n <= 5000

Brute Force Approach:

Intuition:

Given a number, all its divisors can be counted. Since a prime number has only two divisors, which are 1 and the number itself, the count of divisors for a prime number will always be 2. If the given number has two divisors, then it is prime, else it is not.

Approach:

  1. Initialize a counter with 0 to store the number of divisors.
  2. Start iterating from 1 to the number using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable. If it is divisible completely, increment the counter by 1.
  3. After the iterations are over, the counter stores the number of divisors the given number had. If the counter is equal to 2, the number is prime, else it is not.

Dry Run:

Initially
N = 5
count = 0
First Pass
i = 1
N % i == 0
5 % 1 == 0
True

count = count + 1 = 0 + 1 = 1
Second Pass
i = 2
N % i == 0
5 % 2 == 0
False

count = 1, unchanged
Third Pass
i = 3
N % i == 0
5 % 3 == 0
False

count = 1, unchanged
Fourth Pass
i = 4
N % i == 0
5 % 4 == 0
False

count = 1, unchanged
Fifth Pass
i = 5
N % i == 0
5 % 5 == 0
True

count = count + 1 = 1 + 1 = 2
i = 6, i has exceeded N, so the loop would terminate

Code

bool isPrime(int n) {
        
        /* Variable to store the 
        count of divisors of n */
        int count = 0;
        
        // Loop from 1 to n
        for (int i = 1; i <= n; ++i) {
            
            // Check if i is a divisor
            if (n % i == 0) {
                // Increment Count
                count = count + 1;
            }
        }
        
        // If count is 2, n is prime
        if (count == 2) return true;
        // Else not prime
        return false;
    }

Complexity Analysis:

  • Time Complexity: O(N) – Looping N times to find the count of all divisors of N.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Optimal Approach:

Intuition:

The algorithm can be optimized by only iterating up to the square root of n when checking for divisors. This is because if n has a divisor i, then another divisor (counterpart divisor) for n is (n/i).

Approach:

  1. Initialize a counter with 0 to store the number of divisors.
  2. Start iterating from 1 to the square root of the number using a loop variable, and check whether the number is divisible completely (leaving the remainder zero) by the loop variable. If it is divisible completely, increment the counter by 1. Also, if the counterpart divisor is not the same as the divisor, increment the counter by 1.
  3. After the iterations are over, the counter stores the number of divisors the given number had. If the counter is equal to 2, the number is prime, else it is not.

Code

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

class Solution {
public:
    /* Function to find whether the
    number is prime or not */
    bool isPrime(int n) {
        
        /* Variable to store the 
        count of divisors of n */
        int count = 0;
        
        // Loop from 1 to square root of n
        for(int i = 1; i <= sqrt(n); ++i) {
            
            // Check if i is a divisor
            if(n % i == 0) {
                // Increment Count
                count = count + 1;
                
                /* Check if counterpart divisor
                is different from original divisor */
                if(n % i != i) {
                    
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        if(count == 2) return true;
        // Else not prime
        return false;
    }
};

int main() {
    int n = 5;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find whether the
    given number is prime or not */
    bool ans = sol.isPrime(n);
    
    if(ans) {
        cout << n << " is a prime number." << endl;
    } else {
        cout << n << " is not a prime number." << endl;
    }
    
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(sqrt(N)) – Looping sqrt(N) times to find the count of all divisors of N.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

1️⃣1️⃣ Count of prime numbers till N

You are given an integer n. You need to find out the number of prime numbers in the range [1, n] (inclusive). Return the number of prime numbers in the range.

A prime number is a number which has no divisors except, 1 and itself.

Examples:

Example 1
Input: n = 6

Output: 3

Explanation: Prime numbers in the range [1, 6] are 2, 3, 5.
Example 2
Input: n = 10

Output: 4

Explanation: Prime numbers in the range [1, 10] are 2, 3, 5, 7.

Constraints:

2 <= n <= 1000
Note:

Can you come up with a solution with time complexity less than O(n2)?

Brute Force Approach

Intuition:

A naive approach to count prime numbers till N, is to check every number starting from 1 till N for prime. Keep a counter to store the count. If the number is prime, increment the counter. Once all the numbers are checked, the counter stores the required count.

Approach:

  1. Initialize a counter to store the count of prime numbers.
  2. Iterate from 2 to n, and check the current value for prime (using the brute way). If found prime, increment the counter by 1.
  3. After the iterations are over, the counter stores the required result.

Dry Run:

Initially
N = 5
count = 0

Iterate from 2 to N and check for each number whether it is prime or not.
i = 2, check for prime (cnt = 0)
for j = 1
	2%j == 0
	2%1 == 0, cnt = cnt + 1 = 1
for j = 2
	2%j == 0
	2%2 == 0, cnt = cnt + 1 = 1 + 1 = 2
cnt equals 2, hence 2 is a prime number

Code:

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

class Solution {
private:
    /* Function to find whether the
    number is prime or not */
    bool isPrime(int n) {
        
        /* Variable to store the 
        count of divisors of n */
        int count = 0;
        
        // Loop from 1 to n
        for (int i = 1; i <= n; ++i) {
            
            // Check if i is a divisor
            if (n % i == 0) {
                // Increment count
                count = count + 1;
            }
        }
        
        // If count is 2, n is prime
        if (count == 2) return true;
        // Else not prime
        return false;
    }
    
public:
    /* Function to find count
    of primes till n */
    int primeUptoN(int n) {
        
        // Variable to store count
        int count = 0;
        
        // Iterate from 1 to n
        for (int i = 2; i <= n; i++) {
            
            // Check if i is prime
            if (isPrime(i)) count++;
        }
        
        // Return the count
        return count;
    }
};

int main() {
    int n = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get 
    count of all primes till n */
    int ans = sol.primeUptoN(n);
    
    cout << "The count of primes till " << n << " is: " << ans;
    
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(N2) – Checking all numbers from 1 to n for prime and checking if a number is prime or not will take O(n) TC.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Optimal Approach:

Intuition:

The previous approach can be optimized by improving the complexity of the function to find whether a number is prime or not.

Approach:

  1. Initialize a counter to store the count of prime numbers.
  2. Iterate from 2 to n, and check the current value for prime (using the optimal way). If found prime, increment the counter by 1.
  3. After the iterations are over, the counter stores the required result.

Code:

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

class Solution {
private:
    /* Function to find whether the
    number is prime or not */
    bool isPrime(int n) {
        
        /* Variable to store the 
        count of divisors of n */
        int count = 0;
        
        // Loop from 1 to square root of n
        for(int i = 1; i <= sqrt(n); ++i) {
            
            // Check if i is a divisor
            if(n % i == 0) {
                // Increment count
                count = count + 1;
                
                /* Check if counterpart divisor
                is different from original divisor */
                if(n % i != i) {
                    
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        if(count == 2) return true;
        // Else not prime
        return false;
    }
    
public:
    /* Function to find count
    of primes till n */
    int primeUptoN(int n) {
        
        // Variable to store count
        int count = 0;
        
        // Iterate from 1 to n
        for (int i = 2; i <= n; i++) {
            
            // Check if i is prime
            if (isPrime(i)) count++;
        }
        
        // Return the count
        return count;
    }
};

int main() {
    int n = 6;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to get 
    count of all primes till n */
    int ans = sol.primeUptoN(n);
    
    cout << "The count of primes till " << n << " is: " << ans;
    
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(N3/2) – Checking all numbers from 1 to N for prime and checking if a number is prime or not will take O(N1/2) TC.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

1️⃣2️⃣ GCD (Greatest Common Divisor) || HCF of two numbers

You are given two integers n1 and n2. You need find the Greatest Common Divisor (GCD) of the two given numbers. Return the GCD of the two numbers.

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both of the integers.

Examples:

Example 1
Input: n1 = 4, n2 = 6

Output: 2

Explanation: Divisors of n1 = 1, 2, 4, Divisors of n2 = 1, 2, 3, 6

Greatest Common divisor = 2.
Example 2
Input: n1 = 9, n2 = 8

Output: 1

Explanation: Divisors of n1 = 1, 3, 9 Divisors of n2 = 1, 2, 4, 8.

Greatest Common divisor = 1.

Constraints:

1 <= n1, n2 <= 1000
Note:

Can you come up with a solution with less than O(n) time complexity?

Brute Force Approach

Intuition:

The GCD (Greatest Common Divisor), also known as HCF (Highest Common Factor), of two numbers is the largest number that divides both without leaving a remainder. To find the GCD, check all numbers from 1 up to the smaller of the two input numbers for common factors. The largest of these common factors is the GCD.

Approach:

  1. Initialize a variable gcd with 1 that will store the greatest common divisor of the two given numbers.
  2. Iterate from 1 to the minimum of the two numbers using a loop variable. Update the gcd if both the given numbers are divisible by the current value of the loop variable.
  3. After the iterations are over, the greatest common divisor will be stored in the gcd variable.

Dry Run:

Initially
N1 = 4
N2 = 6
gcd = 1
First Pass
i = 1
	N1 % i == 0 && N2 % i == 0
	4 % 1 == 0 && 6 % 1 == 0
	True
	gcd = 1
Second Pass
i = 2
	N1 % i == 0 && N2 % i == 0
	4 % 2 == 0 && 6 % 2 == 0
	True
	gcd = 2
Third Pass
i = 3
	N1 % i == 0 && N2 % i == 0
	4 % 3 == 0 && 6 % 3 == 0
	False
	gcd = 2, Unchanged
Fourth Pass
i = 4
	N1 % i == 0 && N2 % i == 0
	4 % 4 == 0 && 6 % 4 == 0
	False
	gcd = 2, Unchanged
i = 5
Loop has been terminated, since  i = 5 (greater than min(4, 6))

gcd = 2

return gcd

Code

int GCD(int n1, int n2) {
        
        // Variable to store the gcd
        int gcd = 1;
        
        // Iterate from 1 to min(n1, n2)
        for(int i = 1; i <= min(n1, n2); i++) {
            
            /* Check if i is a common
            divisor of both n1 and n2 */
            if(n1 % i == 0 && n2 % i == 0) {
                
                // Update gcd
                gcd = i;
            }
        }
        
        // Return stored GCD.
        return gcd;
    }

Complexity Analysis:

  • Time Complexity: O(min(N1, N2)) – where N1 and N2 are given numbers. Iterating from 1 to min(N1, N2) and performing constant time operations in each iteration.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Better Approach:

Intuition:

The time complexity of the previous approach can be optimized if we iterate backward from min(n1, n2) to 1. This way the first divisor that is found for both numbers can be returned as the greatest common divisor of the numbers saving unnecessary iterations.

Approach:

  1. Declare a variable gcd that will store the greatest common divisor of the two given numbers.
  2. Iterate from the minimum of the two numbers down to 1 using a loop variable. Update the gcd if both the given numbers are divisible by the current value of the loop variable and break out from the loop to save unnecessary iterations.
  3. The greatest common divisor for the two numbers is stored in the gcd variable which can be returned as the answer.

Dry Run:

Initially
N1 = 4
N2 = 6
gcd = 1
First Pass
i = 4 (miniumum of N1 and N2)
	N1 % i == 0 && N2 % i == 0
	4 % 4 == 0 && 6 % 4 == 0
	False
	gcd = 1, Unchanged

Decrement i by 1
Second Pass
i = 3
	N1 % i == 0 && N2 % i == 0
	4 % 3 == 0 && 6 % 3 == 0
	False
	gcd = 1, Unchanged

Decrement i by 1
Third Pass
i = 2
	N1 % i == 0 && N2 % i == 0
	4 % 2 == 0 && 6 % 2 == 0
	True
	gcd = 2

Terminate the loop here and return the gcd

Code:

int GCD(int n1, int n2) {
        
        // Variable to store the gcd
        int gcd;
        
        // Iterate from 1 to min(n1, n2)
        for(int i = min(n1, n2); i >= 1; --i) {
            
            /* Check if i is a common
            divisor of both n1 and n2 */
            if(n1 % i == 0 && n2 % i == 0) {
                
                // Update gcd
                gcd = i;
                // Break to skip unnecessary iterations
                break;
            }
        }
        
        // Return stored GCD.
        return gcd;
    }

Complexity Analysis:

  • Time Complexity: O(min(N1, N2)) – where N1 and N2 are given numbers. In the worst case, finding GCD will require iterating from min(N1, N2) till 1 and performing constant time operations in each iteration.
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Optimal Approach:

Intuition:

The most optimal way to solve this problem is to use the Euclidean Algorithm which works on the principle that the GCD of two numbers remains the same even if the smaller number is subtracted from the larger number.

Euclidean Algorithm:

To find the GCD of n1 and n2 where n1 > n2:

  • Repeatedly subtract the smaller number from the larger number until one of them becomes 0.
  • Once one of them becomes 0, the other number is the GCD of the original numbers.
Example: GCD of n1 = 7, n2 = 2 can be found in this way:
gcd(7, 2) = gcd(7-2, 2) = gcd(5, 2)
gcd(5, 2) = gcd(5-2, 2) = gcd(3, 2)
gcd(3, 2) = gcd(3-2, 2) = gcd(1, 2)
gcd(2, 1) = gcd(2-1, 1) = gcd(1, 1)
gcd(1, 1) = gcd(1-1, 1) = gcd(0, 1)
Hence GCD of n1 = 7, n2 = 2 is 1.

Note:

Observe that instead of subtracting the smaller number from the greater number repeatedly, the modulus operator can be used.
gcd(7, 2) = gcd(7%2, 2) = gcd(1, 2)

Approach:

  1. Initialize a while loop till both numbers are greater than zero.
  2. In each iteration perform the modulus operation of the greater number with the smaller number.
  3. Once the loop terminates, one of the two variables stores a non-zero value which is the GCD for the given pair of numbers.

Dry Run:

Initially
N1 = 4
N2 = 6
gcd = 1
First Pass
N1 < N2
	4 < 6
	True
	N2 = N2 % N1
	N2 = 6 % 4 = 2
	N2 = 2

In each iteration perform the modulus operation of the greater number with the smaller number.
Second Pass
N1 > N2
	4 < 2
	True
	N1 = N1 % N2
	N1 = 4 % 2 = 0
	N1 = 0

In each iteration perform the modulus operation of the greater number with the smaller number.
N1 = 0
N2 = 2
gcd = 2

Loop terminated, gcd is n2 since N1 equals 0.

Code:

int GCD(int n1, int n2) {
        
        /* Continue loop as long as both 
         n1 and n2 are greater than zero */
        while(n1 > 0 && n2 > 0) {
            
            /* If n1 is greater than n2, perform
             modulo operation - n1 % n2 */
            if(n1 > n2) {
                n1 = n1 % n2;
            }
            
            /* Else perform modulo
            operation - n2 % n1 */
            else {
                n2 = n2 % n1;
            }
        }
        
        // If n1 is zero, GCD is stored in n2
        if(n1 == 0) return n2;
        
        //else GCD is stored in n1
        return n1;
    }

Complexity Analysis:

  • Time Complexity: O(log(min(N1, N2))) – where N1 and N2 are given numbers. Because in every iteration, the algorithm is dividing larger number with the smaller number resulting in time complexity.(approx.)
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

1️⃣3️⃣ LCM of two numbers

You are given two integers n1 and n2. You need find the Lowest Common Multiple (LCM) of the two given numbers. Return the LCM of the two numbers.

The Lowest Common Multiple (LCM) of two integers is the lowest positive integer that is divisible by both the integers.

Examples:

Example 1
Input: n1 = 4, n2 = 6

Output: 12

Explanation: 4 * 3 = 12, 6 * 2 = 12.

12 is the lowest integer that is divisible both 4 and 6.
Example 2
Input: n1 = 3, n2 = 5

Output: 15

Explanation: 3 * 5 = 15, 5 * 3 = 15.

15 is the lowest integer that is divisible both 3 and 5.

Constraints:

1 <= n1, n2 <= 1000
Note:

Can you come up with a solution with less than O(n) time complexity?

Intuition:

In a naive approach to finding the LCM of two given numbers, the multiples of the larger number (considering multiples of the larger number instead of the smaller number will trim unfruitful iterations) can be checked if it is common for both numbers. Any such multiple found will be common to both the given numbers, and that will be the required LCM.

Approach:

  1. Initialize a variable lcm to store the LCM of given numbers.
  2. Run a loop finding all the multiples of greater number and in every pass, check if the multiple is common for both numbers. If found common, store the multiple as lcm and terminate the loop.
  3. The LCM for the two numbers will be stored in variable lcm.

Dry Run:

N1 = 6
N2 = 4
n = max(N1, N2) = max(6, 4) = 6
First Pass
i = 1
	mul = n * i = 6 * 1 = 6
	mul % N1 != 0 && mul % N2 != 0
i = 2
	mul = n * i = 6 * 2 = 12
	mul % N1 == 0 && mul % N2 == 0
	12 % 6 == 0 && 12 % 4 == 0
	
for i = 2, common factor is found.
mul = 12
Hence LCM of N1 and N2 is mul

Code:

int LCM(int n1,int n2) {
        //Variable to store lcm
        int lcm;
        
        // Variable to store max of n1 & n2
        int n = max(n1, n2);
        int i = 1;
        
        while(1) {
            // Variable to store multiple
            int mul = n * i;
            
            /* Checking if multiple is common
            common for both n1 and n2 */
            if(mul % n1 == 0 && mul % n2 == 0) {
                lcm = mul;
                break;
            }
            i++;
        }
        
        // Return the stored LCM
        return lcm;
    }

Complexity Analysis:

  • Time Complexity: O(min(N1, N2)) – In the worst-case scenario, when n1 and n2 are coprime, the loop runs for O(n1 * n2 / max(n1, n2)) iterations which is equivalent to O(min(n1, n2)).
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Optimal Approach

Intuition:

The optimal way to find LCM to two numbers is by finding their GCD and using the formula:
lcm(n1, n2) = (n1 * n2) / gcd(n1, n2).

Approach:

  1. Find the GCD of two numbers and store it in some variable.
  2. The LCM for the two numbers can be found directly using the formula mentioned above.

Dry Run:

N1 = 6
N2 = 4
gcd = 2, gcd of (6, 4) = 2
LCM can be computed using given formula:
LCM = (N1 * N2 )/ gcd(N1, N2)
LCM = (6 * 4)/2
LCM = 12

return LCM.

Code:

int GCD(int n1, int n2) {
        
        /* Continue loop as long as both 
         n1 and n2 are greater than zero */
        while(n1 > 0 && n2 > 0) {
            
            /* If n1 is greater than n2, perform
             modulo operation - n1 % n2 */
            if(n1 > n2) {
                n1 = n1 % n2;
            }
            
            /* Else perform modulo
            operation - n2 % n1 */
            else {
                n2 = n2 % n1;
            }
        }
        
        // If n1 is zero, GCD is stored in n2
        if(n1 == 0) return n2;
        
        //else GCD is stored in n1
        return n1;
    }
    

    // Function to find LCM of n1 and n2
    int LCM(int n1,int n2) {
        //Function call to find gcd
        int gcd = GCD(n1, n2);
        
        int lcm = (n1 * n2) / gcd;
        
        // Return the LCM
        return lcm;
    }

Complexity Analysis:

  • Time Complexity: O(log(min(N1, N2))) – Finding GCD of two numbers, along with some constant time operations
  • Space Complexity: O(1) – Using a couple of variables i.e., constant space.

1️⃣4️⃣ Divisors of a number

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:

Example 1
Input: n = 6

Output = [1, 2, 3, 6]

Explanation: The divisors of 6 are 1, 2, 3, 6.
Example 2
Input: n = 8

Output: [1, 2, 4, 8]

Explanation: The divisors of 8 are 1, 2, 4, 8.

Constraints:

  • 1 <= n <= 1000

Brute Force Approach:

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:

  1. Initialize an array/list to store the divisors.
  2. 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.
  3. The array/list stores all the divisors of n.

Dry Run:

N = 6
arr = []
First Pass
i = 1
	N % i == 0
	6 % 1 == 0
	True
	Add i in the array, arr
	arr = [1]
Second Pass
i = 2
	N % i == 0
	6 % 2 == 0
	True
	Add i in the array, arr
	arr = [1, 2]
Third Pass
i = 3
	N % i == 0
	6 % 3 == 0
	True
	Add i in the array, arr
	arr = [1, 2, 3]
Fourth Pass
i = 4
	N % i == 0
	6 % 4 == 0
	False

	arr = [1, 2, 3], Unchanged
Fifth Pass
i = 5
	N % i == 0
	6 % 5 == 0
	False

	arr = [1, 2, 3], Unchanged
Sixth Pass
i = 6
	N % i == 0
	6 % 6 == 0
	True

	arr = [1, 2, 3, 6]

Return arr list

Code:

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;
    }

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.

Optimal Approach:

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:

  1. Initialize an array/list to store the divisors.
  2. 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.
  3. The array/list stores all the divisors of n.

Dry Run:

N = 6
arr = []
First Pass
i = 1
	N % i == 0
	6 % 1 == 0
	True
	Add i in the array list, arr = [1]
	counterDiv = N/i = 6/1, 1 != 6
	arr = [1, 6]
Iterate till i is less than equal to underroot of N.
Second Pass
i = 2
	N % i == 0
	6 % 2 == 0
	True
	Add i in the array list, arr = [1, 2, 6]
	counterDiv = N/i = 6/2 = 3, 3 != 2
	arr = [1, 2, 3, 6]
Iterate till i is less than equal to underroot of N.
Third Pass
i = 3
	3 > square root of 6

arr = [1, 2, 3, 6]
Return the array list.

Code:

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);
                }
            }
        }
        
        // Return the result
        return ans;
    }

Complexity Analysis:

  • Time Complexity: O(sqrt(N)) – Iterating sqrt(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.
Table of Contents
Your experience on this site will be improved by allowing cookies Cookie Policy