Check if a number can be expressed as sum two abundant numbers

0 0 10 minutes read

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 queries
set<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 numbers
void 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 code
int main()
{
    int n = 24;
    SumOfAbundant(n);
    return 0;
}

Java

// Java program to check if number n is expressed
// as sum of two abundant numbers
import 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 function
from 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 numbers
using 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 numbers
 
var N = 100005;
 
// Function to return all abundant numbers
// This function will be helpful for
// multiple queries
function 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 numbers
function 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 queries
function 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 numbers
function 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(n²*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 abundant
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
vector<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 > num
 
 
def 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 result
 
 
if __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 abundant
function 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 N
function 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 numbers
let abundantSum = findAbundantSum(N);
 
if (abundantSum[0] === -1)
    console.log(-1); // If not possible, print -1
else
    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 zambiatek!