Prerequisite: Find all divisors of a natural number
Given a number N. The task is to find all the palindromic divisors of N.
Examples:
Input: N = 66
Output: 1 2 3 6 11 22 33 66Input: N = 808
Output: 1 2 4 8 101 202 404 808
Approach:
- Find all the divisors of N using approach discussed in this article.
- For each divisors D, check whether D is palindromic or not.
- Repeat the above step for all the divisors.
Below is the implementation of the above approach:
C++14
// C++ program to find all the palindromic// divisors of a number#include "bits/stdc++.h"using namespace std;// Function to check is num is palindromic// or notbool isPalindrome(int n){ // Convert n to string str string str = to_string(n); // Starting and ending index of // string str int s = 0, e = str.length() - 1; while (s < e) { // If char at s and e are // not equals then return // false if (str[s] != str[e]) { return false; } s++; e--; } return true;}// Function to find palindromic divisorsvoid palindromicDivisors(int n){ // To store the palindromic divisors of // number n vector<int> PalindromDivisors; for (int i = 1; i <= sqrt(n); i++) { // If n is divisible by i if (n % i == 0) { // Check if number is a perfect square if (n / i == i) { // Check divisor is palindromic, // then store it if (isPalindrome(i)) { PalindromDivisors.push_back(i); } } else { // Check if divisors are palindrome if (isPalindrome(i)) { PalindromDivisors.push_back(i); } // Check if n / divisors is palindromic // or not if (isPalindrome(n / i)) { PalindromDivisors.push_back(n / i); } } } } // Print all palindromic divisors in sorted order sort(PalindromDivisors.begin(), PalindromDivisors.end()); for (int i = 0; i < PalindromDivisors.size(); i++) { cout << PalindromDivisors[i] << " "; }}// Driver codeint main(){ int n = 66; // Function call to find all palindromic // divisors palindromicDivisors(n);} |
Java
// Java program to find all the palindromic// divisors of a numberimport java.util.*;class GFG{// Function to check is num is palindromic// or notstatic boolean isPalindrome(int n){ // Convert n to String str String str = String.valueOf(n); // Starting and ending index of // String str int s = 0, e = str.length() - 1; while (s < e) { // If char at s and e are // not equals then return // false if (str.charAt(s) != str.charAt(e)) { return false; } s++; e--; } return true;}// Function to find palindromic divisorsstatic void palindromicDivisors(int n){ // To store the palindromic divisors of // number n Vector<Integer> PalindromDivisors = new Vector<Integer>(); for (int i = 1; i <= Math.sqrt(n); i++) { // If n is divisible by i if (n % i == 0) { // Check if number is a perfect square if (n / i == i) { // Check divisor is palindromic, // then store it if (isPalindrome(i)) { PalindromDivisors.add(i); } } else { // Check if divisors are palindrome if (isPalindrome(i)) { PalindromDivisors.add(i); } // Check if n / divisors is palindromic // or not if (isPalindrome(n / i)) { PalindromDivisors.add(n / i); } } } } // Print all palindromic divisors in sorted order Collections.sort(PalindromDivisors); for (int i = 0; i < PalindromDivisors.size(); i++) { System.out.print(PalindromDivisors.get(i)+ " "); }}// Driver codepublic static void main(String[] args){ int n = 66; // Function call to find all palindromic // divisors palindromicDivisors(n);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find all the palindromic # divisors of a numberfrom math import sqrt;# Function to check is num is palindromic # or not def isPalindrome(n) : # Convert n to string str string = str(n); # Starting and ending index of # string str s = 0; e = len(string) - 1; while (s < e) : # If char at s and e are # not equals then return # false if (string[s] != string[e]) : return False; s += 1; e -= 1; return True; # Function to find palindromic divisors def palindromicDivisors(n) : # To store the palindromic divisors of # number n PalindromDivisors = []; for i in range(1, int(sqrt(n))) : # If n is divisible by i if (n % i == 0) : # Check if number is a perfect square if (n // i == i) : # Check divisor is palindromic, # then store it if (isPalindrome(i)) : PalindromDivisors.append(i); else : # Check if divisors are palindrome if (isPalindrome(i)) : PalindromDivisors.append(i); # Check if n / divisors is palindromic # or not if (isPalindrome(n // i)) : PalindromDivisors.append(n // i); # Print all palindromic divisors in sorted order PalindromDivisors.sort(); for i in range(len( PalindromDivisors)) : print(PalindromDivisors[i] ,end=" "); # Driver code if __name__ == "__main__" : n = 66; # Function call to find all palindromic # divisors palindromicDivisors(n); # This code is contributed by AnkitRai01 |
C#
// C# program to find all the palindromic// divisors of a numberusing System;using System.Collections.Generic;class GFG{// Function to check is num is palindromic// or notstatic bool isPalindrome(int n){ // Convert n to String str String str = String.Join("",n); // Starting and ending index of // String str int s = 0, e = str.Length - 1; while (s < e) { // If char at s and e are // not equals then return // false if (str[s] != str[e]) { return false; } s++; e--; } return true;}// Function to find palindromic divisorsstatic void palindromicDivisors(int n){ // To store the palindromic divisors of // number n List<int> PalindromDivisors = new List<int>(); for (int i = 1; i <= Math.Sqrt(n); i++) { // If n is divisible by i if (n % i == 0) { // Check if number is a perfect square if (n / i == i) { // Check divisor is palindromic, // then store it if (isPalindrome(i)) { PalindromDivisors.Add(i); } } else { // Check if divisors are palindrome if (isPalindrome(i)) { PalindromDivisors.Add(i); } // Check if n / divisors is palindromic // or not if (isPalindrome(n / i)) { PalindromDivisors.Add(n / i); } } } } // Print all palindromic divisors in sorted order PalindromDivisors.Sort(); for (int i = 0; i < PalindromDivisors.Count; i++) { Console.Write(PalindromDivisors[i]+ " "); }}// Driver codepublic static void Main(String[] args){ int n = 66; // Function call to find all palindromic // divisors palindromicDivisors(n);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find all the palindromic// divisors of a number// Function to check is num is palindromic// or notfunction isPalindrome(n){ // Convert n to string str var str = (n.toString()); // Starting and ending index of // string str var s = 0, e = str.length - 1; while (s < e) { // If char at s and e are // not equals then return // false if (str[s] != str[e]) { return false; } s++; e--; } return true;}// Function to find palindromic divisorsfunction palindromicDivisors(n){ // To store the palindromic divisors of // number n var PalindromDivisors = []; for(var i = 1; i <= parseInt(Math.sqrt(n)); i++) { // If n is divisible by i if (n % i == 0) { // Check if number is a perfect square if (n / i == i) { // Check divisor is palindromic, // then store it if (isPalindrome(i)) { PalindromDivisors.push(i); } } else { // Check if divisors are palindrome if (isPalindrome(i)) { PalindromDivisors.push(i); } // Check if n / divisors is palindromic // or not if (isPalindrome(n / i)) { PalindromDivisors.push(n / i); } } } } // Print all palindromic divisors in sorted order PalindromDivisors.sort((a, b) => a - b) for(var i = 0; i < PalindromDivisors.length; i++) { document.write( PalindromDivisors[i] + " "); }}// Driver codevar n = 66;// Function call to find all palindromic// divisorspalindromicDivisors(n);// This code is contributed by rrrtnx</script> |
Output:
1 2 3 6 11 22 33 66
Time Complexity: O(N*log N)
Auxiliary Space: O(sqrt(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!
