Keith Number - GeeksforGeeks

Keith Number - GeeksforGeeks
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.

1. Store the ‘n’ digits of given number “x” in an array “terms”.
2. Loop for generating next terms of sequence and adding the previous ‘n’ terms.
3. Keep storing the next_terms from step 2 in array “terms”.
4. 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.

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 trms of a sequence generated

    // using digits of x until we either reach x or a

    // number greate 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);

}

Read full article from Keith Number - GeeksforGeeks