Numer Keitha
Wypróbuj w praktyce GfG 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Liczba n-cyfrowa x nazywana jest liczbą Keitha, jeśli występuje w specjalnej sekwencji (zdefiniowanej poniżej) generowanej z jej cyfr. Sekwencja specjalna ma pierwszych n wyrazów, ponieważ cyfry x, a inne wyrazy są rekurencyjnie oceniane jako suma poprzednich n wyrazów.
Zadanie polega na sprawdzeniu, czy dana liczba jest liczbą Keitha, czy nie.
Przykłady:
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 ...
Algorytm:
- Zapisz „n” cyfr danej liczby „x” w tablicy „terms”.
- Pętla do generowania kolejnych wyrazów sekwencji i dodawania poprzednich „n” wyrazów.
- Kontynuuj przechowywanie next_terms z kroku 2 w tablicy „terms”.
- Jeśli następny wyraz stanie się równy x, wówczas x będzie liczbą Keitha. Jeśli następny wyraz będzie większy niż x, wówczas x nie jest liczbą Keitha.
// C++ program to check if a number is Keith or not #include 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 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
' ) : document . write ( 'No
' ); isKeith ( 12 ) ? document . write ( 'Yes
' ) : document . write ( 'No
' ); isKeith ( 197 ) ? document . write ( 'Yes
' ) : document . write ( 'No
' ); // This code is contributed by _saurabh_jaiswal < /script>
Wyjście:
Yes No Yes
Złożoność czasowa: O(n^2) gdzie n to liczba cyfr
Przestrzeń pomocnicza: NA)
