Número de Keith

Un número x de n dígitos se llama número de Keith si aparece en una secuencia especial (definida a continuación) generada usando sus dígitos. La secuencia especial tiene los primeros n términos como dígitos de x y los demás términos se evalúan recursivamente como la suma de los n términos anteriores.
La tarea es encontrar si un número dado es Keith Number o no.
Ejemplos: 
 

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, ...

Algoritmo: 
 

1. Almacene los ‘n’ dígitos del número dado «x» en una array «términos».
2. Bucle para generar los siguientes términos de secuencia y agregar los términos ‘n’ anteriores.
3. Siga almacenando los next_terms del paso 2 en la array «términos».
4. Si el siguiente término se vuelve igual a x, entonces x es un número de Keith. Si el siguiente término es mayor que x, entonces x no es un número de Keith.

// 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 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 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# 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
?>

<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>

Producción: 

Yes
No
Yes

Complejidad del tiempo: O(n^2) donde n no es ningún dígito

Espacio auxiliar: O(n)
Este artículo es una contribución de Pratik Agarwal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.