Write a Java Program to check if any number is a magic number or not. A number is said to be a magic number if after doing sum of digits in each step and inturn doing sum of digits of that sum, the ultimate result (when there is only one digit left) is 1.

To check if a number is a magic number, we can implement a simple iterative approach. The idea is to keep summing the digits of the number until we reach a single-digit result. Here’s how we can do it:

1. Define the method that will take an integer as input.
2. Loop until the number is greater than 9. Inside the loop:
   • Initialize a variable to hold the sum of digits.
   • Extract each digit using modulo and integer division.
   • Add the digits to the sum.
3. Return true if the result is 1; otherwise, return false.

Here’s the code:

public class MagicNumber {
    public static boolean isMagicNumber(int number) {
        while (number > 9) {
            int sum = 0;
            while (number > 0) {
                sum += number % 10;
                number /= 10;
            }
            number = sum;
        }
        return number == 1;
    }
}

This approach has a time complexity of O(log n) due to the digit extraction, making it efficient for most inputs.

An alternative way to check for a magic number is through recursion. This method leverages the call stack to manage the digit summation. Here’s the step-by-step breakdown:

1. Define a recursive method that takes an integer.
2. Check if the number is less than 10. If it is, return true if it equals 1; otherwise, return false.
3. If not, sum the digits recursively and call the same method with the new sum.

Here’s the implementation:

public class MagicNumber {
    public static boolean isMagicNumber(int number) {
        if (number < 10) {
            return number == 1;
        }
        int sum = 0;
        while (number > 0) {
            sum += number % 10;
            number /= 10;
        }
        return isMagicNumber(sum);
    }
}

This recursive approach simplifies the logic but may have a higher space complexity due to the call stack, particularly for large numbers. The time complexity remains O(log n).

For an optimized solution, we can use properties of numbers to determine if it is a magic number without continuously summing the digits. Specifically, we can leverage the fact that a number is a magic number if it is congruent to 1 modulo 9. Here’s the plan:

1. Check if the number is 0; if so, return false.
2. Use the modulo operator to check if the number is 1 or 0 modulo 9.
3. Return true for 1 and false for others.

Here’s the optimized code:

public class MagicNumber {
    public static boolean isMagicNumber(int number) {
        if (number == 0) return false;
        return number % 9 == 1;
    }
}

This solution is efficient with a time complexity of O(1), as it only involves a few arithmetic operations.