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 ArrayListfindKaprekarNumbers(int begin, int finish) { ArrayList 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 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: 9 10 45 55 99 100yd
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{ 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).