An array arr[] is given to us of distinct numbers such that every element in arr[i] is strictly greater than 1. The task is to create a binary tree, with any number of times that a number may be utilized. The value of each non-leaf node should be equal to the product of the values of its’s children. Return the number of binary trees we make.

Example 1

Input: arr = [2,4]

Output: 3

Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2

Input: arr = [2, 4, 5, 10]

Output: 7

Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2]

Approach 1: Dynamic Programming with HashMap

Dynamic programming efficiently to compute the count of unique binary trees that can formed using the factors of the given numbers.

Algorithm

Step 1: Sort the input array arr in ascending order.

Step 2: Initialize a map dp to store the number of binary trees for each element.

Step 3: Initialize a total count variable.

Step 4: iterate through each number num in the array.

Step 4.1: Initialize a variable count to 1.

Step 4.2: Iterate through each factor, factor of num is less than num:

Step 4.2.1: If factor divides num and dp contains the counts for both num/factor and factor.

Step 4.2.2: Update count by multiplying the counts of these factors and adding it to count.

Step 4.3: Put the updated count of num into the dp map.

Step 4.4: Update the total count.

Step 5: Return the integer value total count.

Filename: BinaryTreesUisngDP1.java

import java.util.Arrays;

import java.util.HashMap;

import java.util.Map;

public class BinaryTreesUisngDP1 {

    private static final int MOD = 1_000_000_007;

    // Method to calculate the number of unique binary trees using dynamic programming

    public int numFactoredBinaryTrees(int[] arr) {

        // Sort the input array

        Arrays.sort(arr);

        // Map to store the count of binary trees for each number

        Map<Integer, Long> dp = new HashMap<>();

        // Variable to store the total count of binary trees

        long total = 0;

        // Iterate through each number in the sorted array

        for (int num : arr) {

            // Initialize the count for the current number

            long count = 1;

            // Iterate through each factor of the current number

            for (int factor : arr) {

                // Break the loop if the factor is greater than or equal to the current number

                if (factor >= num) break;

                // If the factor divides the current number evenly and both factors exist in the map

                if (num % factor == 0 && dp.containsKey(num / factor) && dp.containsKey(factor)) {

                    // Update the count by multiplying the counts of the factors and adding it to the current count

                    count += dp.get(num / factor) * dp.get(factor);

                    // Take the modulo to prevent overflow

                    count %= MOD;

                }

            }

            // Store the count for the current number in the map

            dp.put(num, count);

            // Update the total count by adding the count for the current number

            total += count;

            // Take the modulo to prevent overflow

            total %= MOD;

        }

        // Return the total count of binary trees

        return (int) total;

    }

    // Main method to test the solution

    public static void main(String[] args) {

        BinaryTreesUisngDP1 solution = new BinaryTreesUisngDP1();

        int[] arr = {2, 4, 5, 10};

        System.out.println(solution.numFactoredBinaryTrees(arr));

    }

}

Output

Time Complexity: The time complexity of an algorithm is O(n^2), where n is the number of elements in an array. This is because iterating through each number in the array and inner loop compute counts for each factor.

Space Complexity: The space complexity of an algorithm is O(n). This is because the HashMap used to store counts for each number in the array and constant space for other variables.

Approach 2: Using Recursion

In the recursive approach, we recursively compute the count of binary trees for each number in the input. Using this approach also we can implement the Binary Trees with Factors.

Algorithm

Step 1: Sort the input array.

Step 2: Define a recursive function to calculate the count of binary trees for a given number:

Step 2.1: If the number is 1, return 1.

Step 2.2: Initialize count as 1.

Step 2.3: For each factor of the number:

Step 2.3.1: Recursively calculate the count of binary trees for the left and right factors.

Step 2.3.2: Update the count by adding the product of their counts.

Step 2.4: Return the final count.

Step 3: Iterate through each number in the array and calculate the count using the recursive function.

Step 4: Return the total count modulo MOD as the result.

Filename: BinaryTreesUsingRecursion·java

import java.util.Arrays;

public class BinaryTreesUsingRecursion {

    private static final int MOD = 1_000_000_007;

    public int numFactoredBinaryTrees(int[] arr) {

        Arrays.sort(arr);

        int total = 0;

        for (int num : arr) {

            total += countTrees(num, arr);

            total %= MOD;

        }

        return total;

    }

    private int countTrees(int num, int[] arr) {

        if (num == 1) return 1;

        int count = 1;

        for (int factor : arr) {

            if (factor > Math.sqrt(num)) break;

            if (num % factor == 0 && Arrays.binarySearch(arr, num / factor) >= 0) {

                count += countTrees(factor, arr) * countTrees(num / factor, arr);

                if (factor != num / factor) {

                    count += countTrees(factor, arr) * countTrees(num / factor, arr);

                }

                count %= MOD;

            }

        }

        return count;

    }

    public static void main(String[] args) {

        BinaryTreesUsingRecursion solution = new BinaryTreesUsingRecursion();

        int[] arr = {2, 4};

        System.out.println(solution.numFactoredBinaryTrees(arr)); // Output: 3

    }

}

Output

Complexity Analysis:

Time Complexity: The time complexity of an algorithm is O(n^2), where n is the length of the input array. This is because the sorting step and the nested loop to iterate through factors. Recursive calls are made for each factor, but the depth of recursion is limited by the number of the distinct factors in the array.

Space Complexity: The space complexity is determined by the additional memory used during the recursion. It is influenced by the storage of the input array and other constant space variables used in the algorithm. So, the space complexity of an algorithm is O(n), where n is the length of the input array.

Approach 3: Using Iteration

In the iterative approach, we compute the count of binary trees for each number in the input array· We iterate through each number and its factors·

Algorithm

Step 1: Sort the input array.

Step 2: Initialize a map to store the count of binary trees for each number.

Step 3: Iterate through each number num in the array:

Step 3.1: Initialize count as 1.

Step 3.2: For each number, iterate through factors up to its square root:

Step 3.2.1: If a factor ‘factor’ divides num evenly and num / factor exists in the array:

Step 3.2.2: Update the count by adding the product of the counts of factor and num / factor.

Step 3.2.3: If factor and num / factor are not the same, double the count.

Step 3.2.4: Take the modulo operation with MOD for each count.

Step 3.3: Store the updated count for num in the map.

Step 3.4: Accumulate the count for each num in the total.

Step 4: Return the integer value of total modulo MOD as the result.

Filename: BinaryTreesWithFactorsUsingIteration·java

import java·util·Arrays;

public class BinaryTreesWithFactorsUsingIteration {

    private static final int MOD = 1_000_000_007;

    public int numFactoredBinaryTrees(int[] arr) {

        Arrays·sort(arr);

        long total = 0;

        for (int num : arr) {

            long count = 1;

            for (int factor : arr) {

                if (factor > Math·sqrt(num)) break;

                if (num % factor == 0 && Arrays·binarySearch(arr, num / factor) >= 0) {

                    count += countTrees(factor, arr) * countTrees(num / factor, arr);

                    if (factor != num / factor) {

                        count += countTrees(factor, arr) * countTrees(num / factor, arr);

                    }

                    count %= MOD;

                }

            }

            total += count;

            total %= MOD;

        }

        return (int) total;

    }

    private int countTrees(int num, int[] arr) {

        if (num == 1) return 1;

        int count = 1;

        for (int factor : arr) {

            if (factor > Math·sqrt(num)) break;

            if (num % factor == 0 && Arrays·binarySearch(arr, num / factor) >= 0) {

                count += countTrees(factor, arr) * countTrees(num / factor, arr);

                if (factor != num / factor) {

                    count += countTrees(factor, arr) * countTrees(num / factor, arr);

                }

                count %= MOD;

            }

        }

        return count;

    }

    public static void main(String[] args) {

        Solution solution = new Solution();

        int[] arr = {2, 4};

        System·out·println(solution·numFactoredBinaryTrees(arr)); // Output: 7

    }

}

Output

Time Complexity: The time complexity of an algorithm is O(n^2), where n is the length of the input array. This is because for each number iterating through factors up to its square root.

Space Complexity: The space complexity of an algorithm is O(n), where n is the length of the input array. This is because the input array and other auxiliary space usage.

← Prev Next →

Binary Trees with Factors in Java

Approach 1: Dynamic Programming with HashMap

Approach 2: Using Recursion

Complexity Analysis:

Approach 3: Using Iteration

Algorithm