# Kaprekar Number in Java

In this tutorial, we going to learn about Kaprekar Number in Java. A non-negative integer is called a Kaprekar number if it can be squared and divided into two parts such that the sum equals the original number. The aim is to determine whether a given number is a Kaprekar number or not.

Examples:

Example 1:

Input:  n = 9

Output: Yes

Explanation: 92 = 81 and 8 + 1 is 9

Example 2:

Input: n = 23

Output: No

Explanation: 232 = 529. Neither 5 + 29 nor 29 + 5 is not equal to 23

Example 3:

Input: n = 55

Output: Yes

Explanation:  552 = 3025 and 30 + 25 is 55

## Naïve approach:

Step 1: Enter the integer into isKaprekar() function.

Step 2: Return true if the input is a Kaprekar number and false otherwise.

Step 3: Repeat the process until the squared number can be split in any way if the input number is squared, transformed into a string.

Step 4: Determine whether the total of the two pieces for every split is the same as the initial number.

Step 5: Define the input range for the findKaprekarNumbers() function by start and finish.

Step 6: Moves across the range for every number and call the isKaprekar() function. Step 7: Add the number to an ArrayList of Kaprekar numbers if it is determined to be a Kaprekar number.

Filename: KaprekarNumber.java

`import java.util.ArrayList; public class KaprekarNumber{    // Enter the integer into isKaprekar() function    public static boolean isKaprekar(int number)    {         long squared = (long) number * number;         String squaredString = String.valueOf(squared);         for (int i = 1; i < squaredString.length(); i++)          {             String firstPart = squaredString.substring(0, i);             String secondPart = squaredString.substring(i);             int first = (firstPart.isEmpty()) ? 0 : Integer.parseInt(firstPart);             int second = (secondPart.isEmpty()) ? 0 : Integer.parseInt(secondPart);             if (first + second == number)            {               // Return true if the input is a Kaprekar number and false otherwise.                return true;             }         }         return false;     }    // Define the input range for the findKaprekarNumbers() function by start and finish.    public static ArrayList<Integer> findKaprekarNumbers(int begin, int finish)   {         ArrayList<Integer> kaprekarNumbers = new ArrayList<>();         for (int i = begin; i <= finish; i++)       {             if (isKaprekar(i))           {                 kaprekarNumbers.add(i);             }         }         return kaprekarNumbers;     }     public static void main(String[] args)   {         int beginRange = 1;         int finishRange = 200;         ArrayList<Integer> kaprekarNumbers = findKaprekarNumbers(beginRange, finishRange);         System.out.println("Kaprekar Numbers between " + beginRange + " and " + finishRange + ":");         for (int number : kaprekarNumbers)       {             System.out.println(number);         }     } }`

Output:

`Kaprekar Numbers between 1 and 200:910455599100yd`

Time complexity: The time complexity of the program is O(log n).

Space complexity: The space complexity of the program is O(1).

## Approach 1: Using direct computation and verification

### ALGORITHM:

Step 1: Check if n is equal to 1.

Step 2: Count the number of digits in the square of n.

Step 3: Iterate through each possible splits of the square.

Filename: KaprekarNumber.java

`public class KaprekarNumber{    // Returns false otherwise, and true if n is a Kaprekar number.    static boolean iskaprekar(int n)    {                        // If number is equal to 1 then return true        if (n == 1)        return true;        // Count number of digits in square of n        int square_n = n * n;        int countDigits = 0;        while (square_n != 0)        {            countDigits++;            square_n /= 10;        }        square_n = n*n; // As the square changed, recalculate it.Divide the square into several parts and check if the sumis equal to n for any pair of split numbers.        for (int rightDigits=1; rightDigits<countDigits; rightDigits++)        {            int equalParts = (int) Math.pow(10, rightDigits);            // To stay away from numbers like 10, 100, and 1000 (as they aren't Kaprekar numbers)            if (equalParts == n)                continue;             int sum = square_n/equalParts + square_n % equalParts;            if (sum == n)            return true;        }        return false;    }        public static void main (String[] args)    {        System.out.println("Printing first few Kaprekar Numbers" +                            " using iskaprekar()");        for (int i=1; i<10000; i++)            if (iskaprekar(i))                System.out.print(i + " ");    }}`

Output:

`Printing first few Kaprekar Numbers using iskaprekar()`
`1 9 45 55 99 297 703 999 2223 2728 4879 4950 5050 5292 7272 7777 9999 `

Time complexity: The time complexity of the program is O(n * d).

Space complexity: The space complexity of the program is O(k).