Kaprekar Number

Problem Statement

A number is said to be a kaprekar number if the square of the number is divided into two parts in such a way that the sum of divided parts equals the original number where none of the parts is having a value of 0.

We have given a number to find out whether the number is a kaprekar number or not.

Example

For Example:-

1. Input : number= 55 square of 55= 3025 divided into parts= 30 + 25 = 55 i.e equal to original number
2. Input : number= 99 square of 99 = 9801 divided into parts= 98 + 01 = 99 i.e equal to the original number

If the sum of the divided parts will not be equal the original number then the particular number is not said to be kaprekar number.

For Example:

1. Input : number = 16 square of the number = 256 divided into parts = 25 + 6 or 2 + 56 both of the parts will not be equal to the original number. Hence, it is not a kapreker number.
2. Input : n = 10 square of 10 = 100 after dividing into parts = 100 even if the sum of 10 + 0 is 10 it is not a Kaprekar number. This is because there is a condition for being a kaprekar number which says that none of the parts should be having a value of 0.

Example Explanation:

In the above section as we see numbers like 55 and 99 are kaprekar numbers because when their square is divided into parts, the sum of their divided parts is equal to the original number and numbers like 16 and 10 are not kaprekar numbers.

Let’s discuss them in detail:

In example (1), we have taken 55 as the number to be verified as if it is a kaprekar number or not. First, we find the square of the given number i.e, the square of 55 is 3025. We could divide 3025 in 3 ways (3 + 025), (30 + 25), (302 + 5). As we can see in (30 + 25) case when these divided parts are added together it becomes equal to the original number i.e, 55. Therefore, 55 is a kaprekar number.

In example (3), we have taken 16 as the number to be verified as a kaprekar number. First, we find the square of the number i.e, the square of 16 is 256. So, when the square is divided into two equal parts then it becomes (25 + 6) or (2 + 56). When these divided parts are added together, they will not be equal to the original number i.e, 16. Therefore, 16 is not a kaprekar number.

Constraints

• The value of N, where N is the number to be checked whether it is a kaprekar number or not. 1 <= N <= 10000

Note: The number should be between 1 to 10000.

Approach

In this program, we will find out all the kaprekar numbers between 1 to 100.

Let’s write the algorithm which we will be following to find the numbers:

Algorithm

kaprekarNumber(int num) method:

    - STEP 1: START OF THE METHOD
    - STEP 2: if(num==1) RETURN true
    - STEP 3: square = num*num
    - STEP 4: SET digits = 0
    - STEP 5: APPLY WHILE LOOP WITH STEP 6 and 7 UNTIL (square!=0)
    - STEP 6: INSIDE WHILE LOOP- digits++
    - STEP 7: INSIDE WHILE LOOP- square=square/10
    - STEP 8: AGAIN square = num*num
    - STEP 9: APPLY FOR LOOP WITH STEP 10 to 13 UNTIL i<digits
    - STEP 10: div_parts = pow(10, i)
    - STEP 11: if(div_parts==num) then continue
    - STEP 12: FIND sum = square/div_parts + square%div_parts
    - STEP 13: if(sum==num)
            then RETURN true
    - STEP 14: RETURN false.
    - STEP 15: END OF THE METHOD

main() method:

    - STEP 1: START OF THE METHOD
    - STEP 2: APPLY FOR LOOP TILL i<=100
    - STEP 3: INSIDE FOR LOOP if(kaprekarNumber(i)) THEN Print i
    - STEP 4: END OF THE METHOD

Algorithm Explanation:

In the above algorithm, we have defined a function kaprekarNumber() that has a return type of boolean that checks whether the given number is a kaprekar number or not. Being a boolean return type function it can only return True or False. Inside the kaprekarNumber()function we have initialized a variable square which contains the square of the original number. Then we count the digits of the squared number by the digits variable. Then we divide the squared number at different points and avoid the values like 10, 100, and 1000 because they do not fulfill the condition that we have mentioned above. After dividing the values we find their sum and if the sum is equal to the original number then that number is a kaprekar number means we return true and if not then we return false. Inside the main method, we run a for loop till 100, and then inside the if statement we call the function kaprekarNumber() by passing i as an argument. Therefore, if the kaprekarNumber(i) function returns true then i is kaprekar number. The for loop will print all kaprekar number till 100.

Now, Let’s see the code implementation of the above algorithm:

Code Implementation

Implementation of the algorithm to find kaprekar numbers between 1 to 100

In C++:-

#include<bits/stdc++.h>
using namespace std;
 
// if sum of divided parts is equal to the original number 
// then func will return true , else return false
bool kaprekarNumber(int num)
{
    // 1 is a kaprekar number therefore always return true
    if (num == 1)
    return true;
 
    // How many digits in square of the number
    int square = num * num;
    int digits = 0;
    while (square!=0)
    {
        digits++;
        square= square/10;
    }
   // Again finding the square as it was changed
    square= num*num; 
 
    // dividing the square of the number at different points
    for (int i=1; i<digits; i++)
    {
        int div_parts = pow(10, i);
 
        // if encounters number like 10,100,1000, program again checks
        if (div_parts == num)
            continue;
 
        // Find sum of divided parts and compare with num whether equal or not
        int sum = square/div_parts + square % div_parts;
        if (sum == num)
        return true;
    }
 
    // if not equal to the original number
    return false;
}
 
// Driver code
int main()
{
    //Printing kaprekar number
    for(int i=1; i<=100; i++)
    {
      if (kaprekarNumber(i))
       {
          cout<<i<<" ";
       }
    }
    
    return 0;
}

In Java:

 class Main{
    // if sum of divided parts is equal to the original number 
    // then func will return true , else return false
    static boolean kaprekarNumber(int num){
        // 1 is a kaprekar number therefore always return true
        if (num == 1)
        return true;
     
        // How many digits in square of the number
        int square = num * num;
        int digits = 0;
        while (square!=0){
            digits++;
            square= square/10;
        }
       // Again finding the square as it was changed
        square= num*num; 
     
        // dividing the square of the number at different points
        for (int i=1; i<digits; i++){
            int div_parts = (int) Math.pow(10, i);
     
            // if encounters number like 10,100,1000, program again checks
            if (div_parts == num)
                continue;
     
            // Find sum of divided parts and compare with num whether equal or not
            int sum = square/div_parts + square % div_parts;
            if (sum == num)
            return true;
        }
     
        // if not equal to the original number
        return false;
    }
    
    // Driver code
    public static void main (String[] args){
        //Printing kaprekar number
        for(int i=1; i<=100; i++){
          if (kaprekarNumber(i)){
              System.out.print(i + " ");
           }
        }
        
    }
}

In Python:

import math
 
# if sum of divided parts is equal to the original number 
# then func will return true, else return false
def iskaprekar(num):
    if num == 1 :
        return True
     
    # How many digits in square of the number
    square = num * num
    digits = 1
    while not square == 0 :
        digits = digits + 1
        square = square // 10
     
    square = num * num  # Again finding the square as it was changed
     
    # dividing the square of the number at different points
    i = 0
    while i< digits :
        i = i + 1
        div_parts = (int) (math.pow(10, i))
         
        # if encounters number like 10,100,1000, program again checks
        if div_parts == num :
            continue
         
        # Find the sum of divided parts and compare with the num whether equal or not
         
        sum = square//div_parts + square % div_parts
        if sum == num :
            return True
     
    # if not equal to the original number
    return False
     
# Driver method
for i in range(1,100):
    if(iskaprekar(i)):
        print(i,end=" ")
    i = i + 1

Output:

1 9 45 55 99 

Time Complexity

We are using two loops but the loops are not nested, they are one after the other. So, the time complexity comes out to be O(N), where N is number till which we are finding all kaprekar number.

Space Complexity

Since, we are not using any extra space rather than some variable, the space complexity come out to be O(1).

Conclusion

• A number is said to be kaprekar number if the square of the number is divided into two parts in such a way that the sum of divided parts equals the original number where none of the parts is having a value of 0.
• Numbers like 10,100,1000 are not kaprekar numbers as they do not follow the condition which says none of the parts will have a value of 0.
• 1 is the kaprekar number even after having 0 as a value in division (0 + 1) because leading zeros are allowed.