In number theory, a semiperfect number or pseudoperfect number is a natural number n that is equal to the sum of all or some of its proper divisors. A semiperfect number that is equal to the sum of all its proper divisors is a perfect number.
Given a number, the task is to check if the number is a semi-perfect number or not.
Examples:
Input: 40
Output: The number is Semiperfect
1+4+5+10+20=40Input: 70
Output: The number is not Semiperfect
The first few semiperfect numbers are
6, 12, 18, 20, 24, 28, 30, 36, 40
Approach: Store all the factors of the number in a data-structure(Vector or Arrays). Sort them in increasing order. Once the factors are stored, Dynamic programming can be used to check if any combination forms N or not. The problem becomes similar to the Subset Sum Problem. We can use the same approach and check if the number is a semi-perfect number or not.
Below is the implementation of the above approach.
C++
// C++ program to check if the number// is semi-perfect or not#include <bits/stdc++.h>using namespace std;// code to find all the factors of// the number excluding the number itselfvector<int> factors(int n){ // vector to store the factors vector<int> v; v.push_back(1); // note that this loop runs till sqrt(n) for (int i = 2; i <= sqrt(n); i++) { // if the value of i is a factor if (n % i == 0) { v.push_back(i); // condition to check the // divisor is not the number itself if (n / i != i) { v.push_back(n / i); } } } // return the vector return v;}// Function to check if the// number is semi-perfect or notbool check(int n){ vector<int> v; // find the divisors v = factors(n); // sorting the vector sort(v.begin(), v.end()); int r = v.size(); // subset to check if no is semiperfect bool subset[r + 1][n + 1]; // initialising 1st column to true for (int i = 0; i <= r; i++) subset[i][0] = true; // initializing 1st row except zero position to 0 for (int i = 1; i <= n; i++) subset[0][i] = false; // loop to find whether the number is semiperfect for (int i = 1; i <= r; i++) { for (int j = 1; j <= n; j++) { // calculation to check if the // number can be made by summation of divisors if (j < v[i - 1]) subset[i][j] = subset[i - 1][j]; else { subset[i][j] = subset[i - 1][j] || subset[i - 1][j - v[i - 1]]; } } } // if not possible to make the // number by any combination of divisors if ((subset[r][n]) == 0) return false; else return true;}// driver code to check if possibleint main(){ int n = 40; if (check(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java program to check // if the number is // semi-perfect or notimport java.util.*;class GFG{// Code to find all the factors of// the number excluding the number itselfstatic Vector<Integer> factors(int n){ // vector to store the factors Vector<Integer> v = new Vector<>(); v.add(1); // note that this loop runs till Math.sqrt(n) for (int i = 2; i <= Math.sqrt(n); i++) { // if the value of i is a factor if (n % i == 0) { v.add(i); // condition to check the // divisor is not the number itself if (n / i != i) { v.add(n / i); } } } // return the vector return v;}// Function to check if the// number is semi-perfect or notstatic boolean check(int n){ Vector<Integer> v = new Vector<>(); // find the divisors v = factors(n); // sorting the vector Collections.sort(v); int r = v.size(); // subset to check if no // is semiperfect boolean [][]subset = new boolean[r + 1][n + 1]; // initialising 1st column to true for (int i = 0; i <= r; i++) subset[i][0] = true; // initializing 1st row except // zero position to 0 for (int i = 1; i <= n; i++) subset[0][i] = false; // loop to find whether the // number is semiperfect for (int i = 1; i <= r; i++) { for (int j = 1; j <= n; j++) { // calculation to check if the // number can be made by // summation of divisors if (j < v.elementAt(i - 1)) subset[i][j] = subset[i - 1][j]; else { subset[i][j] = subset[i - 1][j] || subset[i - 1][j - v.elementAt(i - 1)]; } } } // If not possible to make the // number by any combination of divisors if ((subset[r][n]) == false) return false; else return true;}// Driver code to check if possiblepublic static void main(String[] args){ int n = 40; if (check(n)) System.out.print("Yes"); else System.out.print("No");}}// This code is contributed by gauravrajput1 |
Python3
# Python3 program to check if the number# is semi-perfect or notimport math# code to find all the factors of# the number excluding the number itselfdef factors( n): # vector to store the factors v = [] v.append(1) # note that this loop runs till sqrt(n) sqt = int(math.sqrt(n)) for i in range(2, sqt + 1): # if the value of i is a factor if (n % i == 0): v.append(i) # condition to check the # divisor is not the number itself if (n // i != i): v.append(n // i) # return the vector return v# Function to check if the# number is semi-perfect or notdef check( n): v = [] # find the divisors v = factors(n) # sorting the vector v.sort() r = len(v) # subset to check if no is semiperfect subset = [[ 0 for i in range(n + 1)] for j in range(r + 1)] # initialising 1st column to true for i in range(r + 1): subset[i][0] = True # initializing 1st row except zero position to 0 for i in range(1, n + 1): subset[0][i] = False # loop to find whether the number is semiperfect for i in range(1, r + 1): for j in range(1, n + 1): # calculation to check if the # number can be made by summation of divisors if (j < v[i - 1]): subset[i][j] = subset[i - 1][j]; else: subset[i][j] = (subset[i - 1][j] or subset[i - 1][j - v[i - 1]]) # if not possible to make the # number by any combination of divisors if ((subset[r][n]) == 0): return False else: return True# Driver Codeif __name__ == "__main__": n = 40 if (check(n)): print("Yes") else: print("No")# This code is contributed by ChitraNayal |
C#
// C# program to check // if the number is // semi-perfect or notusing System;using System.Collections.Generic;class GFG{// Code to find all the // factors of the number // excluding the number itselfstatic List<int> factors(int n){ // vector to store the factors List<int> v = new List<int>(); v.Add(1); // note that this loop runs // till Math.Sqrt(n) for (int i = 2; i <= Math.Sqrt(n); i++) { // if the value of i is // a factor if (n % i == 0) { v.Add(i); // condition to check the // divisor is not the number // itself if (n / i != i) { v.Add(n / i); } } }// return the vectorreturn v;}// Function to check if the// number is semi-perfect or notstatic bool check(int n){ List<int> v = new List<int>(); // find the divisors v = factors(n); // sorting the vector v.Sort(); int r = v.Count; // subset to check if no // is semiperfect bool [,]subset = new bool[r + 1, n + 1]; // initialising 1st column // to true for (int i = 0; i <= r; i++) subset[i, 0] = true; // initializing 1st row except // zero position to 0 for (int i = 1; i <= n; i++) subset[0, i] = false; // loop to find whether the // number is semiperfect for (int i = 1; i <= r; i++) { for (int j = 1; j <= n; j++) { // calculation to check if the // number can be made by // summation of divisors if (j < v[i - 1]) subset[i, j] = subset[i - 1, j]; else { subset[i, j] = subset[i - 1, j] || subset[i - 1, (j - v[i - 1])]; } } } // If not possible to make // the number by any combination // of divisors if ((subset[r, n]) == false) return false; else return true;}// Driver code public static void Main(String[] args){ int n = 40; if (check(n)) Console.Write("Yes"); else Console.Write("No");}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to check// if the number is// semi-perfect or not// Code to find all the factors of// the number excluding the number itselffunction factors(n){ // vector to store the factors let v = []; v.push(1); // note that this loop runs till Math.sqrt(n) for (let i = 2; i <= Math.sqrt(n); i++) { // if the value of i is a factor if (n % i == 0) { v.push(i); // condition to check the // divisor is not the number itself if (Math.floor(n / i) != i) { v.push(Math.floor(n / i)); } } } // return the vector return v;}// Function to check if the// number is semi-perfect or notfunction check(n){ let v = [] ; // find the divisors v = factors(n); // sorting the vector v.sort(function(a,b){return a-b;}); let r = v.length; // subset to check if no // is semiperfect let subset = new Array(r + 1); for(let i=0;i<r+1;i++) { subset[i]=new Array(n+1); for(let j=0;j<n+1;j++) { subset[i][j]=false; } } // initialising 1st column to true for (let i = 0; i <= r; i++) subset[i][0] = true; // initializing 1st row except // zero position to 0 for (let i = 1; i <= n; i++) subset[0][i] = false; // loop to find whether the // number is semiperfect for (let i = 1; i <= r; i++) { for (let j = 1; j <= n; j++) { // calculation to check if the // number can be made by // summation of divisors if (j < v[i-1]) subset[i][j] = subset[i - 1][j]; else { subset[i][j] = subset[i - 1][j] || subset[i - 1][j - v[i-1]]; } } } // If not possible to make the // number by any combination of divisors if ((subset[r][n]) == false) return false; else return true;}// Driver code to check if possiblelet n = 40;if (check(n)) document.write("Yes");else document.write("No"); // This code is contributed by rag2127</script> |
Output
Yes
Time Complexity: O(number of factors * N)
Auxiliary Space: O(number of factors * N)
Efficient approach : Space optimization
In previous approach the current value subset[i][j] is only depend upon the current and previous row values of subset matrix. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation:
C++
// C++ program to check if the number// is semi-perfect or not#include <bits/stdc++.h>using namespace std;// code to find all the factors of// the number excluding the number itselfvector<int> factors(int n){ // vector to store the factors vector<int> v; v.push_back(1); // note that this loop runs till sqrt(n) int sqrtN = sqrt(n); for (int i = 2; i <= sqrtN; i++) { // if the value of i is a factor if (n % i == 0) { v.push_back(i); // condition to check the // divisor is not the number itself if (n / i != i) { v.push_back(n / i); } } } // return the vector return v;}// Function to check if the// number is semi-perfect or notbool check(int n){ vector<int> v; // find the divisors v = factors(n); // sorting the vector sort(v.begin(), v.end()); int r = v.size(); // initialize to store computations of subproblems vector<bool> subset(n + 1, false); // Base Case subset[0] = true; // iterate over subproblems to get the current // value from previous computations for (int i = 0; i < r; i++) { for (int j = n; j >= v[i]; j--) { subset[j] = subset[j] || subset[j - v[i]]; } } // return final answer return subset[n];}// Driver Codeint main(){ int n = 40; if (check(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
import java.util.ArrayList;import java.util.Collections;public class Main { // Function to find all the factors of the number excluding the number itself static ArrayList<Integer> factors(int n) { // ArrayList to store the factors ArrayList<Integer> v = new ArrayList<>(); v.add(1); // Note that this loop runs till sqrt(n) int sqrtN = (int) Math.sqrt(n); for (int i = 2; i <= sqrtN; i++) { // If the value of i is a factor if (n % i == 0) { v.add(i); // Condition to check the divisor is not the number itself if (n / i != i) { v.add(n / i); } } } // Return the ArrayList of factors return v; } // Function to check if the number is semi-perfect or not static boolean check(int n) { ArrayList<Integer> v; // Find the divisors v = factors(n); // Sorting the ArrayList Collections.sort(v); int r = v.size(); // Initialize an array to store computations of subproblems boolean[] subset = new boolean[n + 1]; // Base Case subset[0] = true; // Iterate over subproblems to get the current // value from previous computations for (int i = 0; i < r; i++) { for (int j = n; j >= v.get(i); j--) { subset[j] = subset[j] || subset[j - v.get(i)]; } } // Return the final answer return subset[n]; } // Driver Code public static void main(String[] args) { int n = 40; if (check(n)) System.out.println("Yes"); else System.out.println("No"); }} |
Python3
import math# Function to find all the factors of# the number excluding the number itselfdef factors(n): # List to store the factors v = [1] # Note that this loop runs till sqrt(n) sqrtN = int(math.sqrt(n)) for i in range(2, sqrtN + 1): # If the value of i is a factor if n % i == 0: v.append(i) # Condition to check the # divisor is not the number itself if n // i != i: v.append(n // i) # Return the list return v# Function to check if the# number is semi-perfect or notdef check(n): v = [] # Find the divisors v = factors(n) # Sorting the list v.sort() r = len(v) # Initialize to store computations of subproblems subset = [False] * (n + 1) # Base Case subset[0] = True # Iterate over subproblems to get the current # value from previous computations for i in range(r): for j in range(n, v[i] - 1, -1): subset[j] = subset[j] or subset[j - v[i]] # Return final answer return subset[n]# Driver Codeif __name__ == "__main__": n = 40 if check(n): print("Yes") else: print("No") |
C#
using System;using System.Collections.Generic;class Program{ // Function to find all the factors of the number excluding the number itself static List<int> Factors(int n) { // List to store the factors List<int> factorsList = new List<int>(); factorsList.Add(1); // Note that this loop runs until sqrt(n) int sqrtN = (int)Math.Sqrt(n); for (int i = 2; i <= sqrtN; i++) { // If the value of i is a factor if (n % i == 0) { factorsList.Add(i); // Condition to check that the divisor is not the number itself if (n / i != i) { factorsList.Add(n / i); } } } // Return the list return factorsList; } // Function to check if the number is semi-perfect or not static bool CheckSemiPerfect(int n) { List<int> factorsList = new List<int>(); // Find the divisors factorsList = Factors(n); // Sorting the list factorsList.Sort(); int r = factorsList.Count; // Initialize an array to store computations of subproblems bool[] subset = new bool[n + 1]; // Base Case subset[0] = true; // Iterate over subproblems to get the current value from previous computations for (int i = 0; i < r; i++) { for (int j = n; j >= factorsList[i]; j--) { subset[j] = subset[j] || subset[j - factorsList[i]]; } } // Return the final answer return subset[n]; } // Driver Code static void Main() { int n = 40; if (CheckSemiPerfect(n)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }}// This code is contributed by shivamgupta0987654321 |
Javascript
// Function to find all the factors of a number excluding the number itselffunction factors(n) { const v = [1]; // Array to store the factors const sqrtN = Math.sqrt(n); for (let i = 2; i <= sqrtN; i++) { // If i is a factor if (n % i === 0) { v.push(i); // Check if the divisor is not the number itself if (n / i !== i) { v.push(n / i); } } } // Return the array of factors return v;}// Function to check if the number is semi-perfect or notfunction check(n) { let v = []; // Find the divisors v = factors(n); // Sort the array v.sort((a, b) => a - b); const r = v.length; // Initialize an array to store computations of subproblems const subset = Array(n + 1).fill(false); // Base Case subset[0] = true; // Iterate over subproblems to get the current // value from previous computations for (let i = 0; i < r; i++) { for (let j = n; j >= v[i]; j--) { subset[j] = subset[j] || subset[j - v[i]]; } } // Return the final answer return subset[n];}// Driver Codeconst n = 40;if (check(n)) { console.log("Yes");} else { console.log("No");} |
Output
Yes
Time Complexity: O(number of factors * N)
Auxiliary Space: O(N)
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!
