Lynch-Bell Number in Java

Introduction:

Lynch-Bell Number is N if its digits are distinct and N is divisible by each digit.

A Lynch-Bell Number must meet these two conditions:

• All its digits are distinct.
• The number is divisible by each of its digits.

Example:

Lynch-Bell number in the range of 1 to 100:

1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 24, 36, 48

Approach: Brute Force Approach

Algorithm:

Step 1: Initialize a loop to iterate through numbers in the specified range (from start to end).

Step 2: For each number in the loop

Step 2.1: Convert the number to a string to analyze its digits. Initialize a boolean array digitSeen of size 10 (for digits 0 to 9). This array will track whether each digit has been seen.

Step 2.2: Initialize a boolean variable isLynchBell to true, assuming the number is a Lynch-Bell Number initially.

Step3: Inside the loop, do the following for each digit of the number

Step 3.1: Convert the digit character to an integer. Check if this digit has been seen before (i.e. if digitSeen[digit] is true). If it has been seen, set isLynchBell to false.

Step 4: If isLynchBell is still true after checking all digits, proceed to the divisibility check:

Step 4.1: Iterate through each digit of the number. Convert the digit character to an integer. Check if the digit is 0 or if the number is not divisible by the digit (i.e., num % digit != 0). If either condition is met, set isLynchBell to false.

Step 5: If isLynchBell remains true after both checks, it means the number is a Lynch-Bell Number. Display or store the number as a result.

Step 6: After the loop, the program has searched for Lynch-Bell Numbers within the specified range and displayed/stored the results accordingly.

Filename: LynchBellNumberFinder.java

public class LynchBellNumberFinder {

    public static void main(String[] args) {

        int start = 1; // Starting point of the search

        int end = 1000; // Ending point of the search

        System.out.println("Lynch-Bell Numbers within the range " + start + " to " + end + ":");

        for (int num = start; num <= end; num++) {

            if (isLynchBellNumber(num)) {

                System.out.print(num + " ");

            }

        }

    }

    public static boolean isLynchBellNumber(int num) {

        // Convert the number to a string to check the digits

        String numStr = Integer.toString(num);

        // Checking of distinct digits

        boolean[] digitSeen = new boolean[10]; // We assume numbers are base-10

        for (char digitChar : numStr.toCharArray()) {

            int digit = digitChar - '0';

            if (digitSeen[digit]) {

                return false; // If all digits are not distinct

            }

            digitSeen[digit] = true;

        }

        // Checking the divisibility condition

        for (char digitChar : numStr.toCharArray()) {

            int digit = digitChar - '0';

            if (digit == 0 || num % digit != 0) {

                return false; // If the number is not divisible by all its digits

            }

        }

        return true; // If all conditions satisfied

    }

}

Output:

Lynch-Bell Numbers within the range 1 to 1000:

1 2 3 4 5 6 7 8 9 12 15 24 36 48 124 126 128 132 135 162 168 175 184 216 248 264 312 315 324 384 396 412 432 612 624 648 672 728 735 784 816 824 864 936

Time Complexity:

The isLynchBellNumber function is called for each number. This function contains two loops that iterate through the digits of the number, each running a constant number of times (maximum 4 times for base-10 numbers).

The overall time complexity can be approximated as O(n).

Space Complexity:

Variables, such as numStr, digitChar, and digit, store temporary values and do not scale with the input size.

Therefore, the space complexity of the code is constant, represented as O(1).