Given a number N, the task is to check if N is an Untouchable Number or not. If N is an Untouchable Number then print “Yes” else print “No”.
Untouchable Number are numbers which are not the sum of the proper divisors of any number.
Examples:
Input: N = 5
Output: YesInput: N = 20
Output: No
Approach: The idea is to find the sum of the proper divisors of the number N and check if the sum is equals to N or not. If sum is not equals to N, then N is an Untouchable Number then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of// all proper divisors of numint divSum(int num){ // Final result of summation // of divisors int result = 0; // Find all divisors of num for (int i = 2; i <= sqrt(num); i++) { // If 'i' is divisor of 'num' if (num % i == 0) { // If both divisors are same // then add it only once else // add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as // 1 is also a divisor return (result + 1);}// Function to check if N is a// Untouchable Numberbool isUntouchable(int n){ for (int i = 1; i <= 2 * n; i++) { if (divSum(i) == n) return false; } return true;}// Driver Codeint main(){ // Given Number N int N = 52; // Function Call if (isUntouchable(n)) cout << "Yes"; else cout << "No";} |
Java
// Java program for the above approachclass GFG{ // Function to calculate sum of// all proper divisors of numstatic int divSum(int num){ // Final result of summation // of divisors int result = 0; // Find all divisors of num for(int i = 2; i <= Math.sqrt(num); i++) { // If 'i' is divisor of 'num' if (num % i == 0) { // If both divisors are same // then add it only once else // add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as // 1 is also a divisor return (result + 1);}// Function to check if N is a// Untouchable Numberstatic boolean isUntouchable(int n){ for(int i = 1; i <= 2 * n; i++) { if (divSum(i) == n) return false; } return true;}// Driver code public static void main(String[] args) { // Given Number N int n = 52; // Function Call if (isUntouchable(n)) System.out.println("Yes"); else System.out.println("No");} } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approachimport math;# Function to calculate sum of# all proper divisors of numdef divSum(num): # Final result of summation # of divisors result = 0; # Find all divisors of num for i in range(2, int(math.sqrt(num))): # If 'i' is divisor of 'num' if (num % i == 0): # If both divisors are same # then add it only once else # add both if (i == (num // i)): result += i; else: result += (i + num // i); # Add 1 to the result as # 1 is also a divisor return (result + 1);# Function to check if N is a# Untouchable Numberdef isUntouchable(n): for i in range(1, 2 * n): if (divSum(i) == n): return False; return True;# Driver Code# Given Number NN = 52;# Function Callif (isUntouchable(N)): print("Yes");else: print("No");# This code is contributed by Code_Mech |
C#
// C# program for the above approachusing System;class GFG{ // Function to calculate sum of// all proper divisors of numstatic int divSum(int num){ // Final result of summation // of divisors int result = 0; // Find all divisors of num for(int i = 2; i <= Math.Sqrt(num); i++) { // If 'i' is divisor of 'num' if (num % i == 0) { // If both divisors are same // then add it only once else // add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as // 1 is also a divisor return (result + 1);}// Function to check if N is a// Untouchable Numberstatic bool isUntouchable(int n){ for(int i = 1; i <= 2 * n; i++) { if (divSum(i) == n) return false; } return true;}// Driver code public static void Main() { // Given Number N int n = 52; // Function Call if (isUntouchable(n)) Console.Write("Yes"); else Console.Write("No");} } // This code is contributed by Code_Mech |
Javascript
<script>// JavaScript program for the above approach// Function to calculate sum of// all proper divisors of numfunction divSum(num){ // Final result of summation // of divisors let result = 0; // Find all divisors of num for (let i = 2; i <= Math.sqrt(num); i++) { // If 'i' is divisor of 'num' if (num % i == 0) { // If both divisors are same // then add it only once else // add both if (i == (num / i)) result += i; else result += (i + num / i); } } // Add 1 to the result as // 1 is also a divisor return (result + 1);}// Function to check if N is a// Untouchable Numberfunction isUntouchable(n) { for (let i = 1; i <= 2 * n; i++) { if (divSum(i) == n) return false; } return true;}// Driver Code// Given Number nlet n = 52;// Function Callif (isUntouchable(n)) document.write("Yes");else document.write("No");// This code is contributed by blalverma92</script> |
Output:
Yes
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
