Droll Numbers in Java

Introduction:

A Droll number is a number such that the sum of even prime divisors of N is equaled to the sum of odd prime divisors of N. The Droll number concept involves finding numbers for which the sum of even prime divisors equals the sum of odd prime divisors.

Example-1:

Input

Int N = 72

Output

72 is a Droll number.

Explanation:

Prime factorization of 72 = 2*2*2*3*3 = (2^3)*(3^2)

Now,

Sum of even primes = 2+2+2 = 6

Sum of odd primes = 3+3 = 6

Hence, both sum is equal, so 72 is a Droll number.

Example-2:

Input

Int N = 60

Output

60 is not a Droll number.

Explanation:

Prime factorization of 60 = 2*2*3*5 = (2^2)*(3)*(5)

Now,

Sum of even primes = 2+2 = 4

Sum of odd primes = 3+5 = 8

Hence, both are unequal, so 60 is not a Droll number.

Approach: Prime Factorization and Summation Approach

This approach leverages the properties of prime factorization and summation to identify Droll Numbers. It's a direct mathematical approach to solving the problem.

Algorithm:

Step 1: Initialize a function named isDroll that takes an integer n as an argument and returns a boolean value.

Step 1.1: If n equals 1, return false because 1 is not considered a Droll Number.

Step 2: Initialize two variables: sumEven to keep track of the sum of even prime divisors and sumOdd to keep track of the sum of odd prime divisors. Initialize both variables to 0.

Step 2.2: Iterate while n is divisible by 2 (even prime divisor). Increment sumEven by 2. Update n by dividing it by 2.

Step 3: After the above loop, n is now an odd number. Start a loop from 3 to the square root of n, incrementing by 2 in each step (to consider only odd numbers as potential prime divisors).

Step 4: While n is divisible by the current loop variable i. Increment sumOdd by i. Update n by dividing it by i.

Step 5: If n is greater than 2, add n to sumOdd. This handles the case when n is a prime number greater than 2.

Step 6: Check if sumEven is equal to sumOdd. If they are equal, return true, indicating that the number is a Droll Number. Otherwise, return false.

Filename: DrollNumberChecker.java

public class DrollNumberChecker {

    static boolean isDroll(int n) {

        if (n == 1)

            return false;

        // Storing the sum of even prime factors

        int sumEven = 0;

        // Storing the sum of odd prime factors

        int sumOdd = 0;

        // Add the number of 2s that divide n in sumEven

        while (n % 2 == 0) {

            sumEven += 2;

            n = n / 2;

        }

        // n must be odd at this point. So we can skip one element (Note i = i + 2)

        for (int i = 3; i <= Math.sqrt(n); i = i + 2) {

            // While i divides n, add i to sumOdd and divide n

            while (n % i == 0) {

                sumOdd += i;

                n = n / i;

            }

        }

        // This condition is to handle the case when n is a prime

        if (n > 2)

            sumOdd += n;

        // Checking if it's a Droll number

        return sumEven == sumOdd;

    }

    public static void main(String[] args) {

        int n = 60;

        if (isDroll(n))

            System.out.println("Yes,"+" "+n+" "+"is a Droll Number.");

        else

            System.out.println("No,"+" "+n+ " "+"is not a Droll Number.");

    }

}

Output:

Yes, 72 is a Droll Number.   

Time Complexity:

The for loop iterates from 3 to the square root of n, incrementing by 2 in each step (skipping even numbers). The number of iterations in this loop depends on the number of odd prime divisors of n and is generally smaller than O(sqrt(n)).

Hence, the overall time complexity is O(sqrt(n)).

Space Complexity:

sumEven and sumOdd each takes constant space, O(1). The loop variable i also requires constant space, O(1). The input n itself takes constant space, O(1).

Hence, overall space complexity is O(1).