Cunningham Number is a number N of the form , where a, b >= 2.
Few Cunningham numbers are:
3, 5, 7, 8, 9, 10, 15, 17, 24, 26, 28…
Check if N is a Cunningham number
Given a number N, the task is to check if N is an Cunningham Number or not. If N is an Cunningham Number then print “Yes” else print “No”.
Examples:
Input: N = 126
Output: Yes
Explanation:
126 = 5^3+1
Input: N = 16
Output: No
Approach: The idea is to solve the equation in a desired form such that checking that the number is a Cunningham Number or not is easy.
// Cunningham Numbers are the // which can be represented as => =>
Therefore, if or can be expressed in the form of , then the number is cunningham Number.
Below is the implementation of the above approach:
C++
// C++ implementation for the // above approach #include <bits/stdc++.h> using namespace std; // Function to check if a number // can be expressed as a^b. bool isPower( int a) { if (a == 1) return true ; for ( int i = 2; i * i <= a; i++) { double val = log (a) / log (i); if ((val - ( int )val) < 0.00000001) return true ; } return false ; } // Function to check if N is a // Cunningham number bool isCunningham( int n) { return isPower(n - 1) || isPower(n + 1); } // Driver Code int main() { // Given Number int n = 126; // Function Call if (isCunningham(n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation for the above approach import java.util.*; class GFG{ // Function to check if a number // can be expressed as a^b. static boolean isPower( int a) { if (a == 1 ) return true ; for ( int i = 2 ; i * i <= a; i++) { double val = Math.log(a) / Math.log(i); if ((val - ( int )val) < 0.00000001 ) return true ; } return false ; } // Function to check if N is a // Cunningham number static boolean isCunningham( int n) { return isPower(n - 1 ) || isPower(n + 1 ); } // Driver Code public static void main (String[] args) { // Given Number int n = 126 ; // Function Call if (isCunningham(n)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Ritik Bansal |
Python3
# Python3 implementation for the # above approach import math # Function to check if a number # can be expressed as a^b. def isPower(a): if (a = = 1 ): return True i = 2 while (i * i < = a): val = math.log(a) / math.log(i) if ((val - int (val)) < 0.00000001 ): return True i + = 1 return False # Function to check if N is a # Cunningham number def isCunningham(n): return isPower(n - 1 ) or isPower(n + 1 ) # Driver Code # Given Number n = 126 # Function Call if (isCunningham(n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by shubhamsingh10 |
C#
// C# implementation for the // above approach using System; class GFG{ // Function to check if a number // can be expressed as a^b. static bool isPower( int a) { if (a == 1) return true ; for ( int i = 2; i * i <= a; i++) { double val = Math.Log(a) / Math.Log(i); if ((val - ( int )val) < 0.00000001) return true ; } return false ; } // Function to check if N is a // Cunningham number static bool isCunningham( int n) { return isPower(n - 1) || isPower(n + 1); } // Driver Code public static void Main ( string [] args) { // Given number int n = 126; // Function Call if (isCunningham(n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by rock_cool |
Javascript
<script> // Javascript implementation for the above approach // Function to check if a number // can be expressed as a^b. function isPower( a) { if (a == 1) return true ; for ( let i = 2; i * i <= a; i++) { let val = Math.log(a) / Math.log(i); if ((val - parseInt( val) < 0.00000001)) return true ; } return false ; } // Function to check if N is a // Cunningham number function isCunningham(n) { return isPower(n - 1) || isPower(n + 1); } // Driver Code // Given Number let n = 126; // Function Call if (isCunningham(n)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by Rajput-Ji </script> |
Yes
Time Complexity: O(n1/2)
Auxiliary Space: O(1)
Reference: https://oeis.org/A080262
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!