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?> |
Output
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 |
Output
12, 12
Time Complexity: O(N * sqrt(N)).
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
