Check whether a given number is an ugly number or not
Given an integer N, the task is to find out whether the given number is an Ugly number or not .
Ugly numbers are numbers whose only prime factors are 2, 3 or 5.
Examples:
Input: N = 14
Output: No
Explanation:
14 is not ugly since it includes another prime factor 7.Input: N = 6
Output: Yes
Explanation:
6 is a ugly since it includes 2 and 3.
Approach: The idea is to use recursion to solve this problem and check if a number is divisible by 2, 3 or 5. If yes then divide the number by that and recursively check that a number is an ugly number or not. If at any time, there is no such divisor, then return false, else true.
Below is the implementation of the above approach:
C++
// C++ implementation to check if a number is an ugly number // or not #include <bits/stdc++.h> using namespace std; // Function to check if a number is an ugly number or not int isUgly( int n) { // Base Cases if (n == 1) return 1; if (n <= 0) return 0; // Condition to check if the number is divided by 2, 3, // or 5 if (n % 2 == 0) return isUgly(n / 2); if (n % 3 == 0) return isUgly(n / 3); if (n % 5 == 0) return isUgly(n / 5); // Otherwise return false return 0; } // Driver Code int main() { int no = isUgly(14); if (no == 1) cout << "Yes" << endl; else cout << "No" << endl; return 0; } // This code is contributed by Sania Kumari Gupta (kriSania804) |
C
// C implementation to check if a number is an ugly number // or not #include <stdio.h> // Function to check if a number is an ugly number or not int isUgly( int n) { // Base Cases if (n == 1) return 1; if (n <= 0) return 0; // Condition to check if the number is divided by 2, 3, // or 5 if (n % 2 == 0) return isUgly(n / 2); if (n % 3 == 0) return isUgly(n / 3); if (n % 5 == 0) return isUgly(n / 5); // Otherwise return false return 0; } // Driver Code int main() { int no = isUgly(14); if (no == 1) printf ( "Yes" ); else printf ( "No" ); return 0; } // This code is contributed by Sania Kumari Gupta (kriSania804) |
Java
// Java implementation to // check if a number is ugly number import java.io.*; public class GFG { // Function to check the ugly // number static int isUgly( int n) { // Base Cases if (n == 1 ) return 1 ; if (n <= 0 ) return 0 ; // Condition to check if // a number is divide by // 2, 3, or 5 if (n % 2 == 0 ) { return (isUgly(n / 2 )); } if (n % 3 == 0 ) { return (isUgly(n / 3 )); } if (n % 5 == 0 ) { return (isUgly(n / 5 )); } return 0 ; } // Driver Code public static void main(String args[]) { int no = isUgly( 14 ); if (no == 1 ) System.out.println( "Yes" ); else System.out.println( "No" ); } } |
Python3
# Python3 implementation to check # if a number is an ugly number # or not # Function to check if a number # is an ugly number or not def isUgly(n): # Base Cases if (n = = 1 ): return 1 if (n < = 0 ): return 0 # Condition to check if the # number is divided by 2, 3, or 5 if (n % 2 = = 0 ): return (isUgly(n / / 2 )) if (n % 3 = = 0 ): return (isUgly(n / / 3 )) if (n % 5 = = 0 ): return (isUgly(n / / 5 )) # Otherwise return false return 0 # Driver Code if __name__ = = "__main__" : no = isUgly( 14 ) if (no = = 1 ): print ( "Yes" ) else : print ( "No" ) # This code is contributed by chitranayal |
C#
// C# implementation to check // if a number is ugly number using System; class GFG{ // Function to check the ugly // number static int isUgly( int n) { // Base Cases if (n == 1) return 1; if (n <= 0) return 0; // Condition to check if // a number is divide by // 2, 3, or 5 if (n % 2 == 0) { return (isUgly(n / 2)); } if (n % 3 == 0) { return (isUgly(n / 3)); } if (n % 5 == 0) { return (isUgly(n / 5)); } return 0; } // Driver Code public static void Main(String []args) { int no = isUgly(14); if (no == 1) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // Javascript implementation to check // if a number is an ugly // number or not // Function to check if a number // is an ugly number or not function isUgly(n) { // Base Cases if (n == 1) return 1; if (n <= 0) return 0; // Condition to check if the // number is divided by 2, 3, or 5 if (n % 2 == 0) { return (isUgly(n / 2)); } if (n % 3 == 0) { return (isUgly(n / 3)); } if (n % 5 == 0) { return (isUgly(n / 5)); } // Otherwise return false return 0; } // Driver Code let no = isUgly(14); if (no == 1) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Mayank Tyagi </script> |
No
Time Complexity: O(log(n))
Auxiliary Space: O(1)
METHOD 2:Using re module.
APPROACH:
The given program checks whether the given number is an ugly number or not. An ugly number is a positive number whose prime factors are only 2, 3, or 5.
ALGORITHM:
1.First, the input number is checked if it is less than or equal to 0, which is not a positive number. If the number is less than or equal to 0, the function returns False.
2.The re.findall() function is used to extract all the occurrences of ‘2’, ‘3’, or ‘5’ digits from the input number’s string representation.
3.The extracted factors are stored in a set to remove any duplicates.
4.The length of the set of extracted factors is compared with the length of the string representation of the input number to check if all the digits are prime factors of 2, 3, or 5.
5.Finally, using the all() function with a lambda function, we check if all the extracted factors are either ‘2’, ‘3’, or ‘5’.
6.If the given number is an ugly number, then the program returns True, and “Yes” is printed. Otherwise, it returns False, and “No” is printed.
C++
#include <iostream> #include <string> #include <set> bool isUgly( int n) { if (n <= 0) { return false ; } std::set< char > factors; std::string numStr = std::to_string(n); for ( char digit : numStr) { if (digit == '2' || digit == '3' || digit == '5' ) { factors.insert(digit); } else { return false ; // If any non-2/3/5 digit is found, return false } } return factors.size() == numStr.size(); } int main() { int n = 14; if (isUgly(n)) { std::cout << "Yes" << std::endl; } else { std::cout << "No" << std::endl; } return 0; } |
Java
import java.util.HashSet; public class Main { static boolean isUgly( int n) { if (n <= 0 ) { return false ; } HashSet<Character> factors = new HashSet<>(); String numStr = Integer.toString(n); for ( char digit : numStr.toCharArray()) { if (digit == '2' || digit == '3' || digit == '5' ) { factors.add(digit); } else { return false ; // If any non-2/3/5 digit is found, return false } } return factors.size() == numStr.length(); } public static void main(String[] args) { int n = 14 ; if (isUgly(n)) { System.out.println( "Yes" ); } else { System.out.println( "No" ); } } } |
Python3
import re def is_ugly(n): if n < = 0 : return False factors = set (re.findall( '2|3|5' , str (n))) return len (factors) = = len ( str (n)) and all ( map ( lambda x: x in [ '2' , '3' , '5' ], factors)) n = 14 if is_ugly(n): print ( "Yes" ) else : print ( "No" ) |
C#
using System; using System.Collections.Generic; class Program { // Function to check if a number is "ugly" (contains // only digits 2, 3, or 5) static bool IsUgly( int n) { if (n <= 0) { return false ; } HashSet< char > factors = new HashSet< char >(); string numStr = n.ToString(); foreach ( char digit in numStr) { if (digit == '2' || digit == '3' || digit == '5' ) { factors.Add(digit); } else { return false ; // If any non-2/3/5 digit is // found, return false } } return factors.Count == numStr.Length; } static void Main() { int n = 14; if (IsUgly(n)) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } |
Javascript
function isUgly(n) { // Check if n is less than or equal to 0 if (n <= 0) { return false ; } // Create a set to store factors let factors = new Set(); // Convert the number to a string let numStr = n.toString(); // Iterate through each digit in the number for (let digit of numStr) { // Check if the digit is 2, 3, or 5 if (digit === '2' || digit === '3' || digit === '5' ) { factors.add(digit); } else { // If any non-2/3/5 digit is found, return false return false ; } } // Check if the number of factors is equal to the length of the string return factors.size === numStr.length; } // Test the function with a sample value (e.g., 14) let n = 14; if (isUgly(n)) { console.log( "Yes" ); // Print "Yes" if the number is ugly } else { console.log( "No" ); // Print "No" if the number is not ugly } |
No
Time Complexity:
The re.findall() function takes linear time proportional to the length of the string representation of the input number. Thus, the time complexity of the program is O(n), where n is the number of digits in the input number.
Auxiliary Space:
The space complexity of the program is O(n) as we are storing the extracted prime factors in a set, which can take up to n space if all the digits in the input number are prime factors of 2, 3, or 5.
Contact Us