Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem statement
1.2.
Sample Example
2.
Approach
2.1.
Finding all the divisors
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024
Medium

Sum of all the subsets whose sum is a Perfect Number from a given array

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This blog will discuss the approach to the sum of all the subsets whose sum is a "perfect number".

Before jumping into the question, let’s learn about the perfect number. So, without any further ado, let’s get started!

What is a Perfect Number?

If the sum of all the proper divisors of a number, excluding the number itself, is equal to the number, it is called a perfect number.

Let us understand it with examples:

Example - 1:

Input: 6
Output: True
Explanation
The divisors of 6 are 3, 2, and 1. The sum of divisors is 1+3+2 = 6 is the number itself. So it is a Perfect Number.

 

Example - 2:

Input: 10
Output: False
Explanation
The divisors of 10 are 2, 5, and 1. The sum of divisors is 1+2+5 = 8, which is not the number itself. So it is not a Perfect Number.

 

Recommended topic about, kth largest element in an array, and Euclid GCD Algorithm

Problem statement

We are given an array having n elements. Our task is to find the sum of all the subsets whose sum is a Perfect Number in the given array.

Sample Example

Input: a[]={6, 3, 2}
Output:  6 
Explanation
The possible subsets of array a[] are:
{6}, {3}, {2}, {6,3}, {6,2}, {3,2}, {6, 3, 2}
Sum of all the subsets:
{6}= 6   // perfect number
{3}= 3  // not a perfect number
{2}= 2   // not a perfect number
{6,3}= 9   // not a perfect number
{6,2}= 8   // not a perfect number
{3,2}= 5   // not a perfect number
{6, 3, 2}= 11    // not a perfect number
Among all the values of the sum of subsets, only 6 is a perfect square. 
So the output is 6.

Approach

The idea is straightforward; we generate all the possible subsets from the given array using a recursive function. We simply pass the sum of the subsets to another function named isPerfectSubsetSum(), where we check whether the passed number is a Perfect Number or not.

In the isPerfectSubsetSum()  function, we calculate all the divisors and then check whether the sum of the divisors equals the number.

Finding all the divisors

All of the divisors are present in pairs if we look closely. For instance, if n = 50, the divisors are (1,50), (2,25), and (5,10). One of the divisors in every pair is present before or till √n.

Sowe can run for loop using this condition (i * i <= n) and find one of the divisors of every pair. Simultaneously we can find the other divisor of the pair by dividing the number with the calculated divisor.

We can significantly speed up our program if we take advantage of finding the divisors using the above efficient approach. If the Number(sum of the subset passed) is a Perfect Number, we just print it.

Let’s understand the above approach with an example:

a[] = {6, 3, 28, 3}
All the possible subsets are: {6}, {3}, {28}, {3}, {6,3}, {6,28}, {6,3}, {3,28}, {28,3}, {3,3}, {6,3,28}, {6,3,3}, {6,28,3}, {3,3,28}, {6,3,28,3}
Perfect subset sums are: 
{6} = 6
{28} = 28   // divisors sum = 1+2+4+7+14 = 28, perfect number
{3,3} = 6

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation in C++

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

int isPerfectSubsetSum(int n)
{
  int sum = 1;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)
    {
      if (i * i != n)
        sum += i + (n / i);
      else
        sum += i;
    }
  }

  if (sum == n) {
    return 1;
  }
  else
    return 0;
}

void subSum(int arr[], int l, int r, int sum = 0)
{

  if (l > r) {


    if (isPerfectSubsetSum(sum)) {
      cout << sum << " ";
    }
    return;
  }


  subSum(arr, l + 1, r, sum + arr[l]);

  subSum(arr, l + 1, r, sum);
}

int main()
{
  int arr[] = { 6, 3, 28, 3 };
  int N = sizeof(arr) / sizeof(arr[0]);
  subSum(arr, 0, N - 1);
  return 0;
}

 

Output:

6 6 28

 

Complexity Analysis

Time complexity: The time complexity is O(total_sum * 2^n) as the number of subsets is 2^n, and for each subset-sum, we are checking, it is a perfect number or not where total_sum is the sum of all elements in the given array.

Space complexity: O(1), as we are using constant extra space.

Frequently Asked Questions

Q1. What is a Perfect Number?

Answer: If the sum of proper divisors of a number, that is, the sum of its positive divisors excluding the number itself, is equal to the number itself, it is said to be a perfect number.

 

Q2. What is the Space Complexity of the function to check whether the given number is a Perfect Number?

Answer: The Space Complexity of the function to check whether the given number is a Perfect Number is √n  as we are using a loop of size √n. 

 

Q3. Why do we have to run a for loop until √n times to find the divisors?

Answer: We have only to run the for loop till √n times to find the divisors because one of the divisors in every pair is present before or up to √n. We can run for loop using this condition (i * i <= num) and find one of the divisors of every pair. Simultaneously we can find the other divisor of the pair by dividing n with the calculated divisor.

Key Takeaways

This article discussed the perfect number and approach to finding the Sum of all the subsets whose sum is a Perfect Number from a given array with examples and C++ code.

Recommended Problems: 

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is absolutely free! 

Thank you for reading!

Previous article
Print all Paths to Escape Out of a Matrix using K Moves
Next article
Minimize operations to transform A to B by multiplying by 2 or appending 1 to it
Live masterclass