Given an integer N, the task is to check if N is a Rare Number.
Rare Number is a number N which is non-palindromic and N+rev(N) and N-rev(N) are both perfect squares where rev(N) is the reverse of the number N. For Example rev(65) = 56
Examples:
Input: N = 65
Output: Yes
65 – 56 = 9 and 65 + 56 = 121 are both perfect squaresInput: N = 10
Output: No
Approach: The idea is to check if N is a palindromic number, then return false. And if it is non-palindromic then just check whether N + rev(N) and N – rev(N) are both perfect squares or not.
Below is the implementation of the above approach:
C++
// C++ implementation to check if // N is a Rare number#include<bits/stdc++.h>using namespace std;// Iterative function to // reverse digits of numint reverseDigits(int num) { int rev_num = 0; while(num > 0) { rev_num = rev_num*10 + num%10; num = num/10; } return rev_num; } // Function to check if N// is perfect squarebool isPerfectSquare(long double x) { // Find floating point value of // square root of x. long double sr = sqrt(x); // If square root is an integer return ((sr - floor(sr)) == 0); } // Function to check if N is an // Rare numberbool isRare(int N){ // Find reverse of N int reverseN = reverseDigits(N); // Number should be non-palindromic if(reverseN == N) return false; return isPerfectSquare(N + reverseN) && isPerfectSquare(N - reverseN);}// Driver Codeint main(){ int n = 65; if (isRare(n)) cout << "Yes"; else cout << "No"; return 0;} |
Java
// Java implementation to check if N// is a Rare numberclass GFG{ // Iterative function to // reverse digits of numstatic int reverseDigits(int num) { int rev_num = 0; while(num > 0) { rev_num = rev_num * 10 + num % 10; num = num / 10; } return rev_num; } // Function to check if N// is perfect squarestatic boolean isPerfectSquare(double x) { // Find floating point value of // square root of x. double sr = Math.sqrt(x); // If square root is an integer return ((sr - Math.floor(sr)) == 0); } // Function to check if N is an // Rare numberstatic boolean isRare(int N){ // Find reverse of N int reverseN = reverseDigits(N); // Number should be non-palindromic if(reverseN == N) return false; return isPerfectSquare(N + reverseN) && isPerfectSquare(N - reverseN);}// Driver code public static void main(String[] args) { int n = 65; if (isRare(n)) { System.out.println("Yes"); } else { System.out.println("No"); }} } // This code is contributed by shubham |
Python3
# Python3 implementation to check if # N is a Rare numberimport math# Iterative function to # reverse digits of numdef reverseDigits(num): rev_num = 0 while(num > 0): rev_num = rev_num * 10 + num % 10 num = num // 10 return rev_num# Function to check if N# is perfect squaredef isPerfectSquare(x): # Find floating point value of # square root of x. sr = math.sqrt(x) # If square root is an integer return ((sr - int(sr)) == 0)# Function to check if N is an # Rare numberdef isRare(N): # Find reverse of N reverseN = reverseDigits(N) # Number should be non-palindromic if(reverseN == N): return False return (isPerfectSquare(N + reverseN) and isPerfectSquare(N - reverseN))# Driver CodeN = 65if (isRare(N)): print("Yes")else: print("No")# This code is contributed by Vishal Maurya |
C#
// C# implementation to check if N// is a Rare numberusing System;class GFG{ // Iterative function to // reverse digits of numstatic int reverseDigits(int num) { int rev_num = 0; while(num > 0) { rev_num = rev_num * 10 + num % 10; num = num / 10; } return rev_num; } // Function to check if N// is perfect squarestatic bool isPerfectSquare(double x) { // Find floating point value of // square root of x. double sr = Math.Sqrt(x); // If square root is an integer return ((sr - Math.Floor(sr)) == 0); } // Function to check if N is an // Rare numberstatic bool isRare(int N){ // Find reverse of N int reverseN = reverseDigits(N); // Number should be non-palindromic if(reverseN == N) return false; return isPerfectSquare(N + reverseN) && isPerfectSquare(N - reverseN);} // Driver code public static void Main(String[] args) { int n = 65; if (isRare(n)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); }} }// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript implementation to check if N// is a Rare number // Iterative function to // reverse digits of num function reverseDigits( num) { let rev_num = 0; while (num > 0) { rev_num = rev_num * 10 + num % 10; num = parseInt(num / 10); } return rev_num; } // Function to check if N // is perfect square function isPerfectSquare( x) { // Find floating point value of // square root of x. let sr = Math.sqrt(x); // If square root is an integer return ((sr - Math.floor(sr)) == 0); } // Function to check if N is an // Rare number function isRare( N) { // Find reverse of N let reverseN = reverseDigits(N); // Number should be non-palindromic if (reverseN == N) return false; return isPerfectSquare(N + reverseN) && isPerfectSquare(N - reverseN); } // Driver code let n = 65; if (isRare(n)) { document.write("Yes"); } else { document.write("No"); }// This code is contributed by todaysgaurav </script> |
Output:
Yes
Time Complexity: O(N1/2)
References: OEIS
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!