Keith Number
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" ); else System.out.println( "No" ); if (isKeith( 197 )) System.out.println( "Yes" ); else System.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" ); else Console.WriteLine( "No" ); if (isKeith(12)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); if (isKeith(197)) Console.WriteLine( "Yes" ); else Console.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)