Keith Number in Java

In this section, we will learn what is Keith number and also create Java Program to check if the given number is Keith or not. The Keith number program frequently asked in Java coding test.

Keith Number

A positive n digit number X is called a Keith number (or repfigit number) if it is arranged in a special number sequence generated using its digits. The special sequence has first n terms as digits of x and other terms are recursively evaluated as the sum of previous n terms. For example, 197, 19, 742, 1537, etc.

Keith Number Example

Let’s check the number 742 is a Keith number or not.

First, we will separate each digit, as 7, 4, 2

To find the next term of the above-created series, we add these digits (i.e. 7+4+2), and the resultant (13) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13

To find the next term of the above series, we add the last three terms (i.e. 13+2+4), and the resultant (19) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19

To find the next term of the above series, we add the last three terms (i.e. 19+13+2), and the resultant (34) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19, 34

To find the next term of the above series, we add the last three terms (i.e. 34+19+13), and the resultant (66) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19, 34, 66

To find the next term of the above series, we add the last three terms (i.e. 66+34+19), and the resultant (119) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19, 34, 66, 119

To find the next term of the above series, we add the last three terms (i.e. 119+66+34), and the resultant (219) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19, 34, 66, 119, 219

To find the next term of the above series, we add the last three terms (i.e. 219+119+66), and the resultant (404) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19, 34, 66, 119, 219, 404

To find the next term of the above series, we add the last three terms (i.e. 404+219+119), and the resultant (742) that we get becomes the next term of the series.

Now, the series becomes, 7, 4, 2, 13, 19, 34, 66, 119, 219, 404, 742

Here, we will stop the process because we get the same number (742) as a term of the series. Hence, the given number 742 is a Keith number.

Keith Number in Java

From the above example, we observe that we need to calculate the terms of the series until we get the same number (that we have taken in starting) as a term of the series.

Note: If the given number (X) has n number of digits, we will recursively add the last n terms of the series. As the number 742 has three digits, so, we have added the last three terms of the series, each time.

Let’s take another example.

Keith Number in Java

Steps to Find Keith Number

  1. Read or initialize a number (X).
  2. Separate each digit from the given number (X).
  3. Add all the n-digits. It gives the next term of the series.
  4. Again, add the last n-terms of the series to find the next term.
  5. Repeat step 4 until we get the term the same as the number we have taken.

Let’s implement the above steps in a Java program.

Keith Number Java Program

The logic is not much difficult. Compute the series using the sum of n previous numbers where n is the number of digits. If one of the numbers computed in the series is the same as the input number, it is a Keith number. The program stops if the value computed is greater than the input number.

Let’s create a Java program and implement the above logic into it.

KeithNumberExample1.java

  1. import java.util.*;  
  2. class KeithNumberExample1  
  3. {  
  4. //user-defined function that checks if the given number is Keith or not  
  5. static boolean isKeith(int x)  
  6. {  
  7. //List stores all the digits of the X  
  8. ArrayList<Integer> terms=new ArrayList<Integer>();  
  9. //n denotes the number of digits   
  10. int temp = x, n = 0;   
  11. //executes until the condition becomes false  
  12. while (temp > 0)  
  13. {  
  14. //determines the last digit of the number and add it to the List      
  15. terms.add(temp%10);  
  16. //removes the last digit  
  17. temp = temp/10;  
  18. //increments the number of digits (n) by 1  
  19. n++;  
  20. }  
  21. //reverse the List  
  22. Collections.reverse(terms);  
  23. int next_term = 0, i = n;  
  24. //finds next term for the series  
  25. //loop executes until the condition returns true  
  26. while (next_term < x)  
  27. {  
  28. next_term = 0;  
  29. //next term is the sum of previous n terms (it depends on number of digits the number has)  
  30. for (int j=1; j<=n; j++)  
  31. next_term = next_term + terms.get(i-j);  
  32. terms.add(next_term);  
  33. i++;  
  34. }  
  35. //when the control comes out of the while loop, there will be two conditions:  
  36. //either next_term will be equal to x or greater than x  
  37. //if equal, the given number is Keith, else not  
  38. return (next_term == x);  
  39. }  
  40. //driver code  
  41. public static void main(String[] args)  
  42. {  
  43. //calling the user-defined method inside the if statement and print the result accordingly    
  44. if (isKeith(19))  
  45. System.out.println(“Yes, the given number is a Keith number.”);  
  46. else  
  47. System.out.println(“No, the given number is not a Keith number.”);  
  48. if(isKeith(742))  
  49. System.out.println(“Yes, the given number is a Keith number.”);  
  50. else  
  51. System.out.println(“No, the given number is not a Keith number.”);  
  52. if(isKeith(4578))  
  53. System.out.println(“Yes, the given number is a Keith number.”);  
  54. else  
  55. System.out.println(“No, the given number is not a Keith number.”);  
  56. }  
  57. }  

Output:

Yes, the given number is a Keith number.
Yes, the given number is a Keith number.
No, the given number is not a Keith number.

Let’s create another Java program to find all the Keith numbers that contain the same number of digits.

KeithNumberExample2.java

  1. import java.util.Scanner;  
  2. public class KeithNumberExample2  
  3. {  
  4. public static void main(String args[])   
  5. {  
  6. Scanner sc= new Scanner(System.in);  
  7. System.out.print(“Enter the number of digits the series must have: “);   
  8. //reads an integer as length of the number from the user  
  9. int numlen = sc.nextInt();  
  10. //checks if the length of the number is greater than 2 or not  
  11. if (numlen < 2)   
  12. {  
  13. //prints if the above condition returns false      
  14. System.out.println(“The number must have at least 2 digits.”);  
  15. }   
  16. //executes if the above condition returns true  
  17. else   
  18. {  
  19. //calculates the lower bound from where the series starts  
  20. long lowBound = (long) Math.pow(10, numlen – 1);  
  21. //calculates the upper bound from where the series ends  
  22. long upperBound = (long) Math.pow(10, numlen);  
  23. for (long l = lowBound; l < upperBound; l++)   
  24. {  
  25. if (isKeith(String.valueOf(l)))   
  26. {  
  27. //prints all the Keith number between given range      
  28. System.out.print(l + “, “);  
  29. }  
  30. }  
  31. }  
  32. sc.close();  
  33. }  
  34. //function that checks whether the given number is Keith or not  
  35. public static boolean isKeith(String input)   
  36. {  
  37. int numlen = input.length();  
  38. //keep track only the last three terms  
  39. long[] series = new long[numlen];  
  40. for (int i = 0; i < numlen; i++)   
  41. {  
  42. series[i] = Long.valueOf(input.substring(i, i + 1));  
  43. }  
  44. long next_term = 0;  
  45. long number = Long.valueOf(input);  
  46. while (next_term < number)   
  47. {  
  48. next_term = 0;    
  49. //calculates next term of the series  
  50. for (int i = 0; i < numlen; i++)   
  51. {  
  52. next_term = next_term + series[i];  
  53. if (i < numlen – 1)   
  54. {  
  55. //shift series to the left      
  56. series[i] = series[i + 1];   
  57. }   
  58. else   
  59. {  
  60. //add new value to the series      
  61. series[i] = next_term;   
  62. }  
  63. }  
  64. //compares the next term of the series with the number and returns boolean value accordingly  
  65. if (next_term == number)   
  66. {  
  67. return true;  
  68. }  
  69. }  
  70. return false;  
  71. }  
  72. }  

Output 1:

Keith Number in Java

Output 2:

Keith Number in Java

Similarly, we can find the d-digit Keith numbers. The following table summarizes the d-digits Keith numbers.

dd-digit Keith Numbers
214, 19, 28, 47, 61, 75
3197, 742
41104, 1537, 2208, 2580, 3684, 4788, 7385, 7647, 7909
531331, 34285, 34348, 55604, 62662, 86935, 93993
6120284, 129106, 147640, 156146, 174680, 183186, 298320, 355419, 694280, 925993
71084051, 7913837
811436171, 33445755, 44121607
9129572008, 251133297
10(none)
1124769286411 96189170155
12171570159070, 202366307758, 239143607789, 296658839738
131934197506555, 8756963649152
1443520999798747, 74596893730427, 97295849958669
15120984833091531, 270585509032586, 754788753590897
163621344088074041, 3756915124022254, 4362827422508274
1711812665388886672, 14508137312404344, 16402582054271374, 69953250322018194, 73583709853303061
18119115440241433462, 166308721919462318, 301273478581322148
191362353777290081176, 3389041747878384662, 5710594497265802190, 5776750370944624064, 6195637556095764016
2012763314479461384279, 27847652577905793413, 45419266414495601903
21855191324330802397989
227657230882259548723593
2326842994422637112523337, 36899277593852609997403, 61333853602129819189668
24229146413136585558461227
259838678687915198599200604

Leave a Comment