Check if the number is an abundant number or not

Problem Statement: Check if the number is an abundant number or not.

Examples:

Example 1:
Input: 18
Output: Abundant Number
Explanation: Divisors of 18 are 1,2,3,6,9. 1+2+3+6+9=21, Since 21 is greater than 18, 18 is an abundant number.

Example 2:
Input: 21
Output: Not Abundant Number
Explanation:Divisors of 21 are 1,3,7. 1+3+7=11, Since 11 is smaller than 21, 11 is not an abundant number.

Definition: If the sum of divisors of a number is greater than the number then it is called abundant number.

Solution 1:Naive approach

Intuition: Traverse from 1 to n and find the divisor of the number.

Approach:

  • Traverse from 1 to n.
  • Maintain a sum variable to store sum of all the divisors of n.
  • If i is a divisor of n then add it to the sum.
  • After the traversal is complete,if the sum is greater than 1,print “yes”,else print “no”.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 18;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		if (n % i == 0) {
			sum += i;
		}
	}
            sum-=n;
	if (sum > n) {
		cout << "Abundant Number" << "\n";
	}
	else {
		cout << "Not Abundant Number" << "\n";
	}

}

Output: Abundant Number

Time Complexity: O(N)

Space Complexity: O(1).

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 18;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
      if (n % i == 0) {
        sum += i;
      }
    }
    sum-=n;
    if (sum > n) {
      System.out.print("Abundant Number");
    } else {
      System.out.print("Not Abundant Number");
    }
  }
}

Output: Abundant Number

Time Complexity: O(N)

Space Complexity: O(1).

Solution 2:Optimized

Intuition: Divisors occur in pairs of i and n/i.For example, if 2 is a divisor of 14 and 14/2 i.e 7 is also a divisor of 14. So now we only need to check from 1 to square root of n.

Approach:

  • Traverse from 1 to square root of n.
  • Maintain a variable sum to calculate sum of divisors.
  • If i is a factor of n,add it to the sum as well as add n/i to the sum.But don’t forget to check if i and n/i are same or not.For instance if i=6 and n=36,then i and n/i will have same value and it will not make sense to add both i and n/i,i.e 6 two times.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 18;
	int sum = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0) {
			if (n / i == i) {
				sum += i;
			}
			else {
				sum += i;
				sum += n / i;
			}
		}
	}
	sum -= n;
	if (sum > n) {
		cout << "Abundant Number" << "\n";
	}
	else {
		cout << "Not Abundant Number" << "\n";
	}

}

Output: Abundant Number

Time Complexity: O(sqrt(n)))

Space Complexity: O(1).

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 18;
    int sum = 0;
    for (int i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        if (n / i == i) {
          sum += i;
        } else {
          sum += i;
          sum += n / i;
        }
      }
    }
    sum -= n;
    if (sum > n) {
      System.out.print("Abundant Number");
    } else {
      System.out.print("Not Abundant Number");
    }
  }
}

Output: Abundant Number

Time Complexity: O(sqrt(n)))

Space Complexity: O(1).

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article