In number theory, a weird number is a natural number that is abundant but not semiperfect. In other words, the sum of the proper divisors (divisors including 1 but not itself) of the number is greater than the number, but no subset of those divisors sums to the number itself.
Given a number N, the task is to check if the number is weird or not.
Examples:
Input: 40
Output: The number is not weird
1+4+5+10+20=40, hence it is not weird.Input: 70
Output: The number is Weird
The smallest weird number is 70. Its proper divisors are 1, 2, 5, 7, 10, 14, and 35; these sum to 74, but no subset of these sums to 70.
The number 12, for example, is abundant but not weird, because the proper divisors of 12 are 1, 2, 3, 4, and 6, which sum to 16; but 2+4+6 = 12. The first few weird numbers are 70, 836, 4030, 5830, 7192, 7912, 9272, 10430, 10570, 10792, 10990, 11410, 11690, 12110, 12530, 12670, 13370, 13510, …
Approach: Check if the number is abundant or not. The approach has been discussed here. Once the checking has been done, check if the number is semiperfect or not. The approach for checking semiperfect numbers has been discussed here.
Below is the implementation of the above approach:
C++
// C++ program to check if the // number is weird 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 abundant or not bool checkAbundant(int n){ vector<int> v; int sum = 0; // find the divisors using function v = factors(n); // sum all the factors for (int i = 0; i < v.size(); i++) { sum += v[i]; } // check for abundant or not if (sum > n) return true; else return false;}// Function to check if the// number is semi-perfect or notbool checkSemiPerfect(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; // initialising 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;}// Function to check for // weird or not bool checkweird(int n){ if (checkAbundant(n) == true && checkSemiPerfect(n) == false) return true; else return false;}// Driver Codeint main(){ int n = 70; if (checkweird(n)) cout << "Weird Number"; else cout << "Not Weird Number"; return 0;} |
Java
// Java program to check if // the number is weird or notimport java.util.*;class GFG{ // code to find all the // factors of the number // excluding the number itselfstatic ArrayList<Integer> factors(int n){ // ArrayList to store // the factors ArrayList<Integer> v = new ArrayList<Integer>(); v.add(1); // note that this loop // runs till 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 ArrayList return v;}// Function to check if the // number is abundant or not static boolean checkAbundant(int n){ ArrayList<Integer> v; int sum = 0; // find the divisors // using function v = factors(n); // sum all the factors for (int i = 0; i < v.size(); i++) { sum += v.get(i); } // check for abundant // or not if (sum > n) return true; else return false;}// Function to check if the// number is semi-perfect or notstatic boolean checkSemiPerfect(int n){ ArrayList<Integer> v; // find the divisors v = factors(n); // sorting the ArrayList 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; // initialising 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.get(i - 1)) subset[i][j] = subset[i - 1][j]; else { subset[i][j] = subset[i - 1][j] || subset[i - 1][j - v.get(i - 1)]; } } } // if not possible to make // the number by any // combination of divisors if ((subset[r][n]) == false) return false; else return true;}// Function to check // for weird or not static boolean checkweird(int n){ if (checkAbundant(n) == true && checkSemiPerfect(n) == false) return true; else return false;}// Driver Codepublic static void main(String args[]){ int n = 70; if (checkweird(n)) System.out.println("Weird Number"); else System.out.println("Not Weird Number");}}// This code is contributed// by Arnab Kundu |
Python3
# Python 3 program to check if the # number is weird or notfrom math import sqrt# 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) for i in range(2, int(sqrt(n)) + 1, 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 (int(n / i) != i): v.append(int(n / i)) # return the vector return v# Function to check if the number # is abundant or not def checkAbundant(n): sum = 0 # find the divisors using function v = factors(n) # sum all the factors for i in range(len(v)): sum += v[i] # check for abundant or not if (sum > n): return True else: return False# Function to check if the# number is semi-perfect or notdef checkSemiPerfect(n): # find the divisors v = factors(n) # sorting the vector v.sort(reverse = False) 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 # initialising 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# Function to check for # weird or not def checkweird(n): if (checkAbundant(n) == True and checkSemiPerfect(n) == False): return True else: return False# Driver Codeif __name__ == '__main__': n = 70 if (checkweird(n)): print("Weird Number") else: print("Not Weird Number") # This code is contributed by# Surendra_Gangwar |
C#
// C# program to check if // the number is weird 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){ // List to store // the factors List<int> v = new List<int>(); v.Add(1); // note that this loop // runs till 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 List return v;}// Function to check if the // number is abundant or not static Boolean checkAbundant(int n){ List<int> v; int sum = 0; // find the divisors // using function v = factors(n); // sum all the factors for (int i = 0; i < v.Count; i++) { sum += v[i]; } // check for abundant // or not if (sum > n) return true; else return false;}// Function to check if the// number is semi-perfect or notstatic Boolean checkSemiPerfect(int n){ List<int> v; // find the divisors v = factors(n); // sorting the List v.Sort(); int r = v.Count; // 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; // initialising 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;}// Function to check // for weird or not static Boolean checkweird(int n){ if (checkAbundant(n) == true && checkSemiPerfect(n) == false) return true; else return false;}// Driver Codepublic static void Main(String []args){ int n = 70; if (checkweird(n)) Console.WriteLine("Weird Number"); else Console.WriteLine("Not Weird Number");}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript program to check if the // number is weird or not// code to find all the factors of// the number excluding the number itselffunction factors(n){ // vector to store the factors var v = []; v.push(1); // note that this loop runs till sqrt(n) for (var 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 (n / i != i) { v.push(n / i); } } } // return the vector return v;}// Function to check if the number // is abundant or not function checkAbundant(n){ var v = []; var sum = 0; // find the divisors using function v = factors(n); // sum all the factors for (var i = 0; i < v.length; i++) { sum += v[i]; } // check for abundant or not if (sum > n) return true; else return false;}// Function to check if the// number is semi-perfect or notfunction checkSemiPerfect(n){ var v = []; // find the divisors v = factors(n); // sorting the vector v.sort() var r = v.length; // subset to check if no is semiperfect var subset = Array.from(Array(r+1), ()=>Array(n+1)); // initialising 1st column to true for (var i = 0; i <= r; i++) subset[i][0] = true; // initialising 1st row except zero position to 0 for (var i = 1; i <= n; i++) subset[0][i] = false; // loop to find whether the number is semiperfect for (var i = 1; i <= r; i++) { for (var 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;}// Function to check for // weird or not function checkweird(n){ if (checkAbundant(n) == true && checkSemiPerfect(n) == false) return true; else return false;}// Driver Codevar n = 70;if (checkweird(n)) document.write( "Weird Number");else document.write( "Not Weird Number");</script> |
Output
Weird Number
Time Complexity: O(N * number of factors)
Auxiliary Space: O(N * number of factors)
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++
#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 (n % i == 0) { v.push_back(i); if (n / i != i) { v.push_back(n / i); } } } // return the vector return v;}// Function to check if the number// is abundant or notbool checkAbundant(int n){ vector<int> v; // find the divisors using function v = factors(n); int sum = 0; // sum all the factors for (int i = 0; i < v.size(); i++) { sum += v[i]; } // check for abundant or not return sum > n;}// Function to check if the// number is semi-perfect or notbool checkSemiPerfect(int n){ vector<int> v; // find the divisors v = factors(n); sort(v.begin(), v.end()); int r = v.size(); // initialize vector to store // computations of subproblems vector<bool> subset(n + 1, false); // Base Case subset[0] = true; // iterate over subproblems using nested loop // to get the computaition of 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 answer return subset[n];}// Function to check for// weird or notbool checkWeird(int n){ return checkAbundant(n) && !checkSemiPerfect(n);}// Driver codeint main(){ int n = 70; if (checkWeird(n)) cout << "Weird Number"; else cout << "Not Weird Number"; 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 until sqrt(n) int sqrtN = (int) Math.sqrt(n); for (int i = 2; i <= sqrtN; i++) { if (n % i == 0) { v.add(i); if (n / i != i) { v.add(n / i); } } } // Return the ArrayList return v; } // Function to check if the number is abundant or not static boolean checkAbundant(int n) { ArrayList<Integer> v; // Find the divisors using the factors function v = factors(n); int sum = 0; // Sum all the factors for (int i = 0; i < v.size(); i++) { sum += v.get(i); } // Check if it's abundant or not return sum > n; } // Function to check if the number is semi-perfect or not static boolean checkSemiPerfect(int n) { ArrayList<Integer> v; // Find the divisors using the factors function v = factors(n); 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 using nested loop // to compute 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 answer return subset[n]; } // Function to check if the number is weird or not static boolean checkWeird(int n) { return checkAbundant(n) && !checkSemiPerfect(n); } // Driver code public static void main(String[] args) { int n = 70; if (checkWeird(n)) System.out.println("Weird Number"); else System.out.println("Not Weird Number"); }} |
Python3
import math# Function to find all factors of n excluding itselfdef factors(n): v = [1] sqrtN = int(math.sqrt(n)) for i in range(2, sqrtN + 1): if n % i == 0: v.append(i) if n // i != i: v.append(n // i) return v# Function to check if the number is abundant or notdef checkAbundant(n): v = factors(n) sum_factors = sum(v) return sum_factors > n# Function to check if the number is semi-perfect or notdef checkSemiPerfect(n): v = factors(n) v.sort() r = len(v) subset = [False] * (n + 1) subset[0] = True for i in range(r): for j in range(n, v[i] - 1, -1): subset[j] = subset[j] or subset[j - v[i]] return subset[n]# Function to check if the number is weird or notdef checkWeird(n): return checkAbundant(n) and not checkSemiPerfect(n)# Driver coden = 70if checkWeird(n): print("Weird Number")else: print("Not Weird Number") |
Javascript
function GFG(n) { const v = [1]; // Note that this loop runs until the square root of n const sqrtN = Math.sqrt(n); for (let i = 2; i <= sqrtN; i++) { if (n % i === 0) { v.push(i); if (n / i !== i) { v.push(n / i); } } } // Return the array of GFG return v;}// Function to check if a number is abundant or notfunction checkAbundant(n) { const v = GFG(n); let sum = 0; // Sum all the factors for (let i = 0; i < v.length; i++) { sum += v[i]; } // Check if the number is abundant return sum > n;}// Function to check if a number is// semi-perfect or notfunction checkSemiPerfect(n) { const v = GFG(n).sort(); const r = v.length; // Initialize an array to store // computations of subproblems const subset = new Array(n + 1).fill(false); // Base Case subset[0] = true; 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 result return subset[n];}// Function to check if a number is weird or notfunction checkWeird(n) { return checkAbundant(n) && !checkSemiPerfect(n);}// Driver codefunction main() { const n = 70; if (checkWeird(n)) { console.log("Weird Number"); } else { console.log("Not Weird Number"); }}// Call the main functionmain(); |
Output
Weird Number
Time Complexity: O(N * number of factors)
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!
