A n digit number x is called Keith number if it appears in a special sequence (defined below) generated using its digits. The special sequence has first n terms as digits of x and other terms are recursively evaluated as sum of previous n terms.
The task is to find if a given number is Keith Number or not.
Examples:
Input : x = 197 Output : Yes 197 has 3 digits, so n = 3 The number is Keith because it appears in the special sequence that has first three terms as 1, 9, 7 and remaining terms evaluated using sum of previous 3 terms. 1, 9, 7, 17, 33, 57, 107, 197, ..... Input : x = 12 Output : No The number is not Keith because it doesn't appear in the special sequence generated using its digits. 1, 2, 3, 5, 8, 13, 21, ..... Input : x = 14 Output : Yes 14 is a Keith number since it appears in the sequence, 1, 4, 5, 9, 14, ...
Algorithm:
- Store the ‘n’ digits of given number “x” in an array “terms”.
- Loop for generating next terms of sequence and adding the previous ‘n’ terms.
- Keep storing the next_terms from step 2 in array “terms”.
- If the next term becomes equal to x, then x is a Keith number. If next term becomes more than x, then x is not a Keith Number.
C++
// C++ program to check if a number is Keith or not #include<bits/stdc++.h> using namespace std; // Returns true if x is Keith, else false. bool isKeith(int x) { // Store all digits of x in a vector "terms" // Also find number of digits and store in "n". vector <int> terms; int temp = x, n = 0; // n is number of digits in x while (temp > 0) { terms.push_back(temp%10); temp = temp/10; n++; } // To get digits in right order (from MSB to // LSB) reverse(terms.begin(), terms.end()); // Keep finding next terms of a sequence generated // using digits of x until we either reach x or a // number greater than x int next_term = 0, i = n; while (next_term < x) { next_term = 0; // Next term is sum of previous n terms for (int j=1; j<=n; j++) next_term += terms[i-j]; terms.push_back(next_term); i++; } /* When the control comes out of the while loop, either the next_term is equal to the number or greater than it. If next_term is equal to x, then x is a Keith number, else not */ return (next_term == x); } // Driver program int main() { isKeith(14)? cout << "Yes\n" : cout << "No\n"; isKeith(12)? cout << "Yes\n" : cout << "No\n"; isKeith(197)? cout << "Yes\n" : cout << "No\n"; return 0; } |
Java
// Java program to check if a number is Keith or not import java.io.*; import java.util.*; class GFG{ // Returns true if x is Keith, else false. static boolean isKeith(int x) { // Store all digits of x in a vector "terms" // Also find number of digits and store in "n". ArrayList<Integer> terms=new ArrayList<Integer>(); int temp = x, n = 0; // n is number of digits in x while (temp > 0) { terms.add(temp%10); temp = temp/10; n++; } // To get digits in right order (from MSB to // LSB) Collections.reverse(terms); // Keep finding next terms of a sequence generated // using digits of x until we either reach x or a // number greater than x int next_term = 0, i = n; while (next_term < x) { next_term = 0; // Next term is sum of previous n terms for (int j=1; j<=n; j++) next_term += terms.get(i-j); terms.add(next_term); i++; } /* When the control comes out of the while loop, either the next_term is equal to the number or greater than it. If next_term is equal to x, then x is a Keith number, else not */ return (next_term == x); } // Driver program public static void main(String[] args) { if (isKeith(14)) System.out.println("Yes"); else System.out.println("No"); if(isKeith(12)) System.out.println("Yes"); elseSystem.out.println("No"); if(isKeith(197)) System.out.println("Yes"); elseSystem.out.println("No"); } } // this code is contributed by mits |
Python3
# Python3 program to check if a number # is Keith or not # Returns true if x is Keith, # else false. def isKeith(x): # Store all digits of x in a vector "terms" # Also find number of digits and store in "n". terms = []; temp = x; n = 0; # n is number of digits in x while (temp > 0): terms.append(temp % 10); temp = int(temp / 10); n+=1; # To get digits in right order # (from MSB to LSB) terms.reverse(); # Keep finding next terms of a sequence # generated using digits of x until we # either reach x or a number greater than x next_term = 0; i = n; while (next_term < x): next_term = 0; # Next term is sum of previous n terms for j in range(1,n+1): next_term += terms[i - j]; terms.append(next_term); i+=1; # When the control comes out of the # while loop, either the next_term is # equal to the number or greater than it. # If next_term is equal to x, then x is a # Keith number, else not return (next_term == x); # Driver Code print("Yes") if (isKeith(14)) else print("No"); print("Yes") if (isKeith(12)) else print("No"); print("Yes") if (isKeith(197)) else print("No"); # This code is contributed by mits |
C#
// C# program to check if a number is Keith or not using System; using System.Collections; class GFG{ // Returns true if x is Keith, else false. static bool isKeith(int x) { // Store all digits of x in a vector "terms" // Also find number of digits and store in "n". ArrayList terms = new ArrayList(); int temp = x, n = 0; // n is number of digits in x while (temp > 0) { terms.Add(temp%10); temp = temp/10; n++; } // To get digits in right order (from MSB to // LSB) terms.Reverse(); // Keep finding next terms of a sequence generated // using digits of x until we either reach x or a // number greater than x int next_term = 0, i = n; while (next_term < x) { next_term = 0; // Next term is sum of previous n terms for (int j=1; j<=n; j++) next_term += (int)terms[i-j]; terms.Add(next_term); i++; } /* When the control comes out of the while loop, either the next_term is equal to the number or greater than it. If next_term is equal to x, then x is a Keith number, else not */ return (next_term == x); } // Driver program public static void Main() { if (isKeith(14)) Console.WriteLine("Yes"); elseConsole.WriteLine("No"); if(isKeith(12)) Console.WriteLine("Yes"); elseConsole.WriteLine("No"); if(isKeith(197)) Console.WriteLine("Yes"); elseConsole.WriteLine("No"); } } // this code is contributed by mits |
PHP
<?php // PHP program to check if a number // is Keith or not // Returns true if x is Keith, // else false. function isKeith($x) { // Store all digits of x in a vector "terms" // Also find number of digits and store in "n". $terms = array(); $temp = $x; $n = 0; // n is number of digits in x while ($temp > 0) { array_push($terms, $temp % 10); $temp = (int)($temp / 10); $n++; } // To get digits in right order // (from MSB to LSB) $terms=array_reverse($terms); // Keep finding next terms of a sequence // generated using digits of x until we // either reach x or a number greater than x $next_term = 0; $i = $n; while ($next_term < $x) { $next_term = 0; // Next term is sum of previous n terms for ($j = 1; $j <= $n; $j++) $next_term += $terms[$i - $j]; array_push($terms, $next_term); $i++; } /* When the control comes out of the while loop, either the next_term is equal to the number or greater than it. If next_term is equal to x, then x is a Keith number, else not */ return ($next_term == $x); } // Driver Code isKeith(14) ? print("Yes\n") : print("No\n"); isKeith(12) ? print("Yes\n") : print("No\n"); isKeith(197) ? print("Yes\n") : print("No\n"); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to check if a number // is Keith or not // Returns true if x is Keith, // else false. function isKeith(x) { // Store all digits of x in a vector "terms" // Also find number of digits and store in "n". let terms = []; let temp = x; let n = 0; // n is number of digits in x while (temp > 0) { terms.push(temp % 10); temp = parseInt(temp / 10); n++; } // To get digits in right order // (from MSB to LSB) terms= terms.reverse(); // Keep finding next terms of a sequence // generated using digits of x until we // either reach x or a number greater than x let next_term = 0; let i = n; while (next_term < x) { next_term = 0; // Next term is sum of previous n terms for (let j = 1; j <= n; j++) next_term += terms[i - j]; terms.push(next_term); i++; } /* When the control comes out of the while loop, either the next_term is equal to the number or greater than it. If next_term is equal to x, then x is a Keith number, else not */ return (next_term == x); } // Driver Code isKeith(14) ? document.write("Yes<br>") : document.write("No<br>"); isKeith(12) ? document.write("Yes<br>") : document.write("No<br>"); isKeith(197) ? document.write("Yes<br>") : document.write("No<br>"); // This code is contributed by _saurabh_jaiswal </script> |
Output:
Yes No Yes
Time complexity: O(n^2) where n is no of digits
Auxiliary Space: O(n)
This article is contributed by Pratik Agarwal. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
