C Program to Check Number is Keith Number or Not

Write a ‘C’ program to check if a number is Keith Number.

  • A Keith number is an n-digit integer (NUM>9) such that if a Fibonacci-like sequence (in which each term in the sequence is the sum of the n previous terms) is formed with the first n terms taken as the decimal digits of the number NUM, then NUM itself occurs as a term in the sequence.

Example:

75 – Keith number
7,5
7+5=12
5+12=17
12+17=29
17+29=46
29+46=75
75 Occurs in the generated sequence and so it is a Keith number.

341 – Not a Keith number
3, 4, 1
3+4+1=8, 
4+1+8=13, 
1+8+13=22, 
8+13+22=43, 
13+22+43=78, 
22+43+78=143
78+43+143=264
43+143+264=450
341 is not a Keith number since it will not occur in the generated sequence.

Input : ‘n’
Output : Yes / No
Constraints:
1 <= ‘n’ <= 10000000

Code:

# include <stdio.h> # include <stdlib.h> int lenCount(int nm) { int ctr=0; while(nm>0) { nm=nm/10; ctr++; } return ctr; } int main() { int num1=0,arr1[10],num2=0,flg=0,i=0,sum=0; scanf("%d",&num1); num2=num1; for(i=lenCount(num2)-1;i>=0;i--) { arr1[i]=num1 % 10; num1/=10; } while(flg==0) { for(i=0;i<lenCount(num2);i++) sum+=arr1[i]; if(sum==num2) { printf("Yes"); flg=1; } if(sum>num2) { printf("No"); flg=1; } for(i=0;i<lenCount(num2);i++) { if(i!=lenCount(num2)-1) arr1[i]=arr1[i+1]; else arr1[i]=sum; } sum=0; } }
Code language: C/AL (cal)

Leave a Comment