Given a number N. The task is to express N as the sum of two Abundant Numbers. If it is not possible, print -1.
Examples:
Input : N = 24
Output : 12, 12
Input : N = 5
Output : -1
Approach: An efficient approach is to store all abundant numbers in a set. And for a given number, N runs a loop from 1 to n and checks if i and n-i are abundant numbers or not.
Below is the implementation of the above approach:
C++
// CPP program to check if number n is expressed// as sum of two abundant numbers#include <bits/stdc++.h>using namespace std;#define N 100005// Function to return all abundant numbers// This function will be helpful for// multiple queriesset<int> ABUNDANT(){ // To store abundant numbers set<int> v; for (int i = 1; i < N; i++) { // to store sum of the divisors // include 1 in the sum int sum = 1; for (int j = 2; j * j <= i; j++) { // if j is proper divisor if (i % j == 0) { sum += j; // if i is not a perfect square if (i / j != j) sum += i / j; } } // if sum is greater than i then i is // a abundant number if (sum > i) v.insert(i); } return v;}// Check if number n is expressed// as sum of two abundant numbersvoid SumOfAbundant(int n){ set<int> v = ABUNDANT(); for (int i = 1; i <= n; i++) { // if both i and n-i are // abundant numbers if (v.count(i) and v.count(n - i)) { cout << i << " " << n - i; return; } } // can not be expressed cout << -1;}// Driver codeint main(){ int n = 24; SumOfAbundant(n); return 0;} |
Java
// Java program to check if number n is expressed// as sum of two abundant numbersimport java.util.*;class GFG { static final int N = 100005;// Function to return all abundant numbers// This function will be helpful for// multiple queries static Set<Integer> ABUNDANT() { // To store abundant numbers Set<Integer> v = new HashSet<>(); for (int i = 1; i < N; i++) { // to store sum of the divisors // include 1 in the sum int sum = 1; for (int j = 2; j * j <= i; j++) { // if j is proper divisor if (i % j == 0) { sum += j; // if i is not a perfect square if (i / j != j) { sum += i / j; } } } // if sum is greater than i then i is // a abundant number if (sum > i) { v.add(i); } } return v; }// Check if number n is expressed// as sum of two abundant numbers static void SumOfAbundant(int n) { Set<Integer> v = ABUNDANT(); for (int i = 1; i <= n; i++) { // if both i and n-i are // abundant numbers if (v.contains(i) & v.contains(n - i)) { System.out.print(i + " " + (n - i)); return; } } // can not be expressed System.out.print(-1); }// Driver code public static void main(String[] args) { int n = 24; SumOfAbundant(n); }}// This code is contributed by 29AjayKumar |
Python 3
# Python 3 program to check if number n is # expressed as sum of two abundant numbers # from math lib import sqrt functionfrom math import sqrt N = 100005# Function to return all abundant numbers # This function will be helpful for # multiple queries def ABUNDANT() : # To store abundant numbers v = set() ; for i in range(1, N) : # to store sum of the divisors # include 1 in the sum sum = 1 for j in range(2, int(sqrt(i)) + 1) : # if j is proper divisor if (i % j == 0) : sum += j # if i is not a perfect square if (i / j != j) : sum += i // j # if sum is greater than i then i # is a abundant numbe if (sum > i) : v.add(i) return v# Check if number n is expressed # as sum of two abundant numbers def SumOfAbundant(n) : v = ABUNDANT() for i in range(1, n + 1) : # if both i and n-i are abundant numbers if (list(v).count(i) and list(v).count(n - i)) : print(i, " ", n - i) return # can not be expressed print(-1) # Driver code if __name__ == "__main__" : n = 24 SumOfAbundant(n)# This code is contributed by Ryuga |
C#
// C# program to check if number n is expressed// as sum of two abundant numbersusing System;using System.Collections.Generic;class GFG { static readonly int N = 100005; // Function to return all abundant numbers // This function will be helpful for // multiple queries static HashSet<int> ABUNDANT() { // To store abundant numbers HashSet<int> v = new HashSet<int>(); for (int i = 1; i < N; i++) { // to store sum of the divisors // include 1 in the sum int sum = 1; for (int j = 2; j * j <= i; j++) { // if j is proper divisor if (i % j == 0) { sum += j; // if i is not a perfect square if (i / j != j) { sum += i / j; } } } // if sum is greater than i then i is // a abundant number if (sum > i) { v.Add(i); } } return v; } // Check if number n is expressed // as sum of two abundant numbers static void SumOfAbundant(int n) { HashSet<int> v = ABUNDANT(); for (int i = 1; i <= n; i++) { // if both i and n-i are // abundant numbers if (v.Contains(i) & v.Contains(n - i)) { Console.Write(i + " " + (n - i)); return; } } // can not be expressed Console.Write(-1); } // Driver code public static void Main() { int n = 24; SumOfAbundant(n); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// javascript program to check if number n is expressed// as sum of two abundant numbersvar N = 100005;// Function to return all abundant numbers// This function will be helpful for// multiple queriesfunction ABUNDANT(){ // To store abundant numbers var v = new Set(); var i,j; for (i = 1; i < N; i++) { // to store sum of the divisors // include 1 in the sum var sum = 1; for (j = 2; j * j <= i; j++) { // if j is proper divisor if (i % j == 0) { sum += j; // if i is not a perfect square if (parseInt(i / j) != j) sum += parseInt(i / j); } } // if sum is greater than i then i is // a abundant number if (sum > i) v.add(i); } return v;}// Check if number n is expressed// as sum of two abundant numbersfunction SumOfAbundant(n){ var v = new Set(); v = ABUNDANT(); var i; for (i = 1; i <= n; i++) { // if both i and n-i are // abundant numbers if (v.has(i) && v.has(n - i)) { document.write(i+ ' ' + (n-i)) return; } } // can not be expressed document.write(-1);}// Driver code var n = 24; SumOfAbundant(n);</script> |
PHP
<?php// PHP program to check if number n is // expressed as sum of two abundant numbers// Function to return all abundant numbers// This function will be helpful for// multiple queriesfunction ABUNDANT(){ $N = 100005; // To store abundant numbers $v = array(); for ($i = 1; $i < $N; $i++) { // to store sum of the divisors // include 1 in the sum $sum = 1; for ($j = 2; $j * $j <= $i; $j++) { // if j is proper divisor if ($i % $j == 0) { $sum += $j; // if i is not a perfect square if ($i / $j != $j) $sum += $i / $j; } } // if sum is greater than i then // i is a abundant number if ($sum > $i) array_push($v, $i); } $v = array_unique($v); return $v;}// Check if number n is expressed// as sum of two abundant numbersfunction SumOfAbundant($n){ $v = ABUNDANT(); for ($i = 1; $i <= $n; $i++) { // if both i and n-i are // abundant numbers if (in_array($i, $v) && in_array($n - $i, $v)) { echo $i, " ", $n - $i; return; } } // can not be expressed echo -1;}// Driver code$n = 24;SumOfAbundant($n);// This code is contributed // by Arnab Kundu?> |
12 12
Time Complexity: O(n2*logn)
Auxiliary Space: O(n)
Another Approach:
- Define a function “isAbundant” to check if a number is an abundant number.
- Iterate from 2 to the square root of the number.
- If the number is divisible by the current iteration, add the divisor and its counterpart to a sum.
- Return true if the sum is greater than the number, indicating it is an abundant number.
- Otherwise, return false.
- Define a function “findAbundantSum” to find two abundant numbers summing up to N.
- Iterate from 1 to N/2
- Check if both the current number and N minus the current number are abundant using the “isAbundant” function.
- If both are abundant, return the pair of numbers.
- If no pair is found, return -1.
- In the main function:
- Set the desired value of N.
- Call the “findAbundantSum” function to get the result.If the result is -1, print -1 indicating no two abundant numbers sum up to N.
- Otherwise, print the pair of abundant numbers.
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;// Function to check if a number is abundantbool isAbundant(int num){ int sum = 1; for (int i = 2; i * i <= num; i++) { if (num % i == 0) { sum += i; if (i != num / i) sum += num / i; } } return sum > num;}// Function to find two abundant numbers summing up to Nvector<int> findAbundantSum(int N){ vector<int> result; for (int i = 1; i <= N / 2; i++) { if (isAbundant(i) && isAbundant(N - i)) { result.push_back(i); result.push_back(N - i); return result; } } result.push_back(-1); return result;}int main(){ int N = 24; // Find the sum of two abundant numbers vector<int> abundantSum = findAbundantSum(N); if (abundantSum[0] == -1) cout << -1 << endl; // If not possible, print -1 else cout << abundantSum[0] << ", " << abundantSum[1] << endl; // Print the two abundant numbers return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { // Function to check if a number is abundant static boolean isAbundant(int num) { int sum = 1; for (int i = 2; i * i <= num; i++) { if (num % i == 0) { sum += i; if (i != num / i) sum += num / i; } } return sum > num; } // Function to find two abundant numbers summing up to N static List<Integer> findAbundantSum(int N) { List<Integer> result = new ArrayList<>(); for (int i = 1; i <= N / 2; i++) { if (isAbundant(i) && isAbundant(N - i)) { result.add(i); result.add(N - i); return result; } } result.add(-1); return result; } public static void main(String[] args) { int N = 24; // Find the sum of two abundant numbers List<Integer> abundantSum = findAbundantSum(N); if (abundantSum.get(0) == -1) System.out.println(-1); // If not possible, print -1 else System.out.println(abundantSum.get(0) + ", " + abundantSum.get(1)); // Print the two abundant numbers // This Code Is Contributed By Shubham Tiwari. }} |
Python3
def is_abundant(num): """ Function to check if a number is abundant """ divisors_sum = 1 for i in range(2, int(num**0.5) + 1): if num % i == 0: divisors_sum += i if i != num // i: divisors_sum += num // i return divisors_sum > numdef find_abundant_sum(N): """ Function to find two abundant numbers summing up to N """ result = [] for i in range(1, N // 2 + 1): if is_abundant(i) and is_abundant(N - i): result.append(i) result.append(N - i) return result result.append(-1) return resultif __name__ == "__main__": N = 24 # Find the sum of two abundant numbers abundant_sum = find_abundant_sum(N) if abundant_sum[0] == -1: print(-1) # If not possible, print -1 else: print(abundant_sum[0], ",", abundant_sum[1]) # Print the two abundant numbers |
C#
using System;using System.Collections.Generic;class GFG { // Function to check if a number is abundant static bool IsAbundant(int num) { int sum = 1; for (int i = 2; i * i <= num; i++) { if (num % i == 0) { sum += i; if (i != num / i) sum += num / i; } } return sum > num; } // Function to find two abundant numbers summing up to N static List<int> FindAbundantSum(int N) { List<int> result = new List<int>(); for (int i = 1; i <= N / 2; i++) { if (IsAbundant(i) && IsAbundant(N - i)) { result.Add(i); result.Add(N - i); return result; } } result.Add(-1); return result; } static void Main(string[] args) { int N = 24; // Find the sum of two abundant numbers List<int> abundantSum = FindAbundantSum(N); if (abundantSum[0] == -1) Console.WriteLine( -1); // If not possible, print -1 else Console.WriteLine( abundantSum[0] + ", " + abundantSum[1]); // Print the two abundant // numbers }} |
Javascript
// Function to check if a number is abundantfunction isAbundant(num) { let sum = 1; for (let i = 2; i * i <= num; i++) { if (num % i === 0) { sum += i; if (i !== num / i) sum += num / i; } } return sum > num;}// Function to find two abundant numbers summing up to Nfunction findAbundantSum(N) { let result = []; for (let i = 1; i <= N / 2; i++) { if (isAbundant(i) && isAbundant(N - i)) { result.push(i); result.push(N - i); return result; } } result.push(-1); return result;}const N = 24;// Find the sum of two abundant numberslet abundantSum = findAbundantSum(N);if (abundantSum[0] === -1) console.log(-1); // If not possible, print -1else console.log(`${abundantSum[0]}, ${abundantSum[1]}`); // Print the two abundant numbers// This Code Is Contributed By Shubham Tiwari |
12, 12
Time Complexity: O(N * sqrt(N)).
Auxiliary Space: O(1).
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Find More here to that Topic: geeksforgeeks.org/check-if-a-number-can-be-expressed-as-sum-two-abundant-numbers/ […]
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/check-if-a-number-can-be-expressed-as-sum-two-abundant-numbers/ […]
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/check-if-a-number-can-be-expressed-as-sum-two-abundant-numbers/ […]