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

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.

## 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
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);
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:

Output 2:

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