Given a number n, We need to check whether n is an aspiring number or not. The number n is called an aspiring number if its aliquot sequence terminates in a perfect number, and it is not a perfect number itself. First few aspiring numbers are : 25, 95, 119, 143, 417, 445, 565, 608, 650, 652….
Examples :
Input : 25 Output : Yes. Explanation : Terminating number of aliquot sequence of 25 is 6 which is perfect number. Input : 24 Output : No. Explanation : Terminating number of aliquot sequence of 24 is 0 which is not a perfect number.
Approach: First we find the terminating number of the aliquot sequence of the given input and then check if it is a perfect number or not (as per definition). Given below is the implementation for checking an aspiring number.
C++
// C++ implementation to check whether// a number is aspiring or not#include <bits/stdc++.h>using namespace std;// Function to calculate sum of all proper// divisorsint getSum(int n){ int sum = 0; // 1 is a proper divisor // Note that this loop runs till square root // of n for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, take only one // of them if (n / i == i) sum = sum + i; else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } // calculate sum of all proper divisors only return sum - n;}// Function to get last number of Aliquot Sequence.int getAliquot(int n){ unordered_set<int> s; s.insert(n); int next = 0; while (n > 0) { // Calculate next term from previous term n = getSum(n); if (s.find(n) != s.end()) return n; s.insert(n); } return 0;}// Returns true if n is perfectbool isPerfect(int n){ // To store sum of divisors long long int sum = 1; // Find all divisors and add them for (long long int i = 2; i * i <= n; i++) if (n % i == 0) sum = sum + i + n / i; // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) return true; return false;}// Returns true if n is aspiring// else returns falsebool isAspiring(int n){ // checking condition for aspiring int alq = getAliquot(n); if (isPerfect(alq) && !isPerfect(n)) return true; else return false;}// Driver programint main(){ int n = 25; if (isAspiring(n)) cout << "Aspiring" << endl; else cout << "Not Aspiring" << endl; return 0;} |
Java
// Java implementation to check whether // a number is aspiring or notimport java.util.*;class GFG { // Function to calculate sum of // all proper divisors static int getSum(int n) { int sum = 0; // 1 is a proper divisor // Note that this loop runs till // square root of n for (int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } // calculate sum of all // proper divisors only return sum - n; } // Function to get last number // of Aliquot Sequence. static int getAliquot(int n) { TreeSet<Integer> s = new TreeSet<Integer>(); s.add(n); int next = 0; while (n > 0) { // Calculate next term from previous term n = getSum(n); if (s.contains(n) & n != s.last()) { return n; } s.add(n); } return 0; } // Returns true if n is perfect static boolean isPerfect(int n) { // To store sum of divisors int sum = 1; // Find all divisors and add them for (int i = 2; i * i <= n; i++) { if (n % i == 0) { sum = sum + i + n / i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) { return true; } return false; } // Returns true if n is aspiring // else returns false static boolean isAspiring(int n) { // checking condition for aspiring int alq = getAliquot(n); if (isPerfect(alq) && !isPerfect(n)) { return true; } else { return false; } } // Driver code public static void main(String[] args) { int n = 25; if (isAspiring(n)) { System.out.println("Aspiring"); } else { System.out.println("Not Aspiring"); } }}/* This code has been contributed by PrinciRaj1992*/ |
Python3
# Python3 implementation to check whether# a number is aspiring or not# Function to calculate sum of all proper# divisorsdef getSum(n): # 1 is a proper divisor sum = 0 # Note that this loop runs till # square root of n for i in range(1, int((n) ** (1 / 2)) + 1): if not n % i: # If divisors are equal, take # only one of them if n // i == i: sum += i # Otherwise take both else: sum += i sum += (n // i) # Calculate sum of all proper # divisors only return sum - n# Function to get last number# of Aliquot Sequence.def getAliquot(n): s = set() s.add(n) next = 0 while (n > 0): # Calculate next term from # previous term n = getSum(n) if n not in s: return n s.add(n) return 0# Returns true if n is perfectdef isPerfect(n): # To store sum of divisors sum = 1 # Find all divisors and add them for i in range(2, int((n ** (1 / 2))) + 1): if not n % i: sum += (i + n // i) # If sum of divisors is equal to # n, then n is a perfect number if sum == n and n != 1: return True return False# Returns true if n is aspiring# else returns falsedef isAspiring(n): # Checking condition for aspiring alq = getAliquot(n) if (isPerfect(alq) and not isPerfect(n)): return True else: return False# Driver Coden = 25if (isAspiring(n)): print("Aspiring")else: print("Not Aspiring")# This code is contributed by rohitsingh07052 |
C#
// C# implementation to check whether // a number is aspiring or notusing System;using System.Collections.Generic; class GFG { // Function to calculate sum of // all proper divisors static int getSum(int n) { int sum = 0; // 1 is a proper divisor // Note that this loop runs till // square root of n for (int i = 1; i <= (int)Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } // calculate sum of all // proper divisors only return sum - n; } // Function to get last number // of Aliquot Sequence. static int getAliquot(int n) { HashSet<int> s = new HashSet<int>(); s.Add(n); while (n > 0) { // Calculate next term from previous term n = getSum(n); if (s.Contains(n)) { return n; } s.Add(n); } return 0; } // Returns true if n is perfect static bool isPerfect(int n) { // To store sum of divisors int sum = 1; // Find all divisors and add them for (int i = 2; i * i <= n; i++) { if (n % i == 0) { sum = sum + i + n / i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) { return true; } return false; } // Returns true if n is aspiring // else returns false static bool isAspiring(int n) { // checking condition for aspiring int alq = getAliquot(n); if (isPerfect(alq) && !isPerfect(n)) { return true; } else { return false; } } // Driver code public static void Main(String[] args) { int n = 25; if (isAspiring(n)) { Console.WriteLine("Aspiring"); } else { Console.WriteLine("Not Aspiring"); } }}// This code is contributed by subhammahato348 |
Javascript
<script>// javascript implementation to check whether // a number is aspiring or not // Function to calculate sum of // all proper divisors function getSum(n) { var sum = 0; // 1 is a proper divisor // Note that this loop runs till // square root of n for (var i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // take only one of them if (n / i == i) { sum = sum + i; } else // Otherwise take both { sum = sum + i; sum = sum + (n / i); } } } // calculate sum of all // proper divisors only return sum - n; } // Function to get last number // of Aliquot Sequence. function getAliquot(n) { var s = new Set(); s.add(n); var next = 0; while (n > 0) { // Calculate next term from previous term n = getSum(n); if (s.has(n) & n != s[s.length-1]) { return n; } s.add(n); } return 0; } // Returns true if n is perfect function isPerfect(n) { // To store sum of divisors var sum = 1; // Find all divisors and add them for (var i = 2; i * i <= n; i++) { if (n % i == 0) { sum = sum + i + n / i; } } // If sum of divisors is equal to // n, then n is a perfect number if (sum == n && n != 1) { return true; } return false; } // Returns true if n is aspiring // else returns false function isAspiring(n) { // checking condition for aspiring var alq = getAliquot(n); if (isPerfect(alq) && !isPerfect(n)) { return true; } else { return false; } } // Driver code var n = 25; if (isAspiring(n)) { document.write("Aspiring"); } else { document.write("Not Aspiring"); }// This code is contributed by gauravrajput1</script> |
Output:
Aspiring
Time Complexity: O(n)
Auxilitary Space Complexity : 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!
