binary-trees-with-factors.py

# 823. Binary Trees With Factors
# 🟠 Medium
#
# https://leetcode.com/problems/binary-trees-with-factors/
#
# Tags: Array - Hash Table - Dynamic Programming

import timeit
from typing import List


# Sort the array, iterate over the sorted values and start computing
# the number of trees that we can obtain with each. Add this number to a
# lookup dictionary. Inside each iteration of the outer loop, we iterate
# over all values of the inner loop that are smaller than the current
# value that we are visiting and check if we can use it to multiply with
# another value to get the outer loop number. If we can, we can use
# these two values as the children of the current root to build a * b
# number of different trees.
#
# Time complexity: O(n^2) - We iterate over the values and, for each one
# iterate over all values smaller than it.
# Space complexity: O(n) - We keep a dictionary of the same size as the
# input.
#
# If we store the modulo values for each entry of seen we use more time
# and less memory:
# Runtime: 933 ms, faster than 27.77%
# Memory Usage: 14 MB, less than 90.91%
#
# If we only compute the modulo at the end, the tests run faster but
# we use more memory:
# Runtime: 649 ms, faster than 54.54%
# Memory Usage: 14.2 MB, less than 30.81%
class DP:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        # If we sort the input, we can start processing the smaller
        # values first.
        arr.sort()
        # Store the number of trees we found so far.
        result = 0
        # Store values that we have seen together with the number of
        # subtrees that can be rooted on them.
        seen = {}
        # Outer loop iterates over the values in the array.
        for i, root in enumerate(arr):
            # Store the number of different combinations we can make
            # with this node as root, the minimum is 1, this node alone.
            sub_trees = 1
            # Inner loop iterates over the values smaller than root.
            # We don't need to check the same value because there are no
            # 1s in the input, factors need to be strictly greater than.
            for j in range(i):
                # Lets call the value we are visiting a, we know a is in
                # seen because we have visited it already.
                a = arr[j]
                # Try to find a value b that we have seen and we can use
                # to multiply with a to make up root.
                if root % a == 0:
                    b = root // a
                    if b in seen:
                        # We can construct a tree with this root and a
                        # and b as children. We will be able to produce
                        # as many different combinations as the product
                        # of their children.
                        sub_trees += seen[a] * seen[b]
            # Store all the number of possible combinations with this
            # node as root. Could modulo the value.
            seen[root] = sub_trees % MOD
            result += seen[root]

        # Return the sum of all the combinations we can make.
        return result % MOD


def test():
    executors = [DP]
    tests = [
        [[2, 4], 3],
        [[2, 4, 5, 10], 7],
        [[2, 4, 5, 10, 20], 18],
        [
            [
                60588000,
                36158400,
                950040,
                162450288,
                446000100,
                1807920,
                31590000,
                360,
                166153680,
                6,
                91213584,
                34186320,
                915124000,
                68600,
                6497400,
                10,
                194304,
                951035904,
                393822000,
                23522400,
                14400,
                821376000,
                80,
                881118000,
                576000,
                3660480,
                106801200,
                180690300,
                5100,
                1573200,
                36288000,
                38,
                197643600,
                221852925,
                8820,
                36000,
                822294528,
                13935240,
                236307456,
                17409600,
                443741760,
                62868,
                548800000,
                25271064,
                34848,
                344137500,
                8383500,
                186,
                45,
                100980,
                722358000,
                63000000,
                16442400,
                1579500,
                684,
                12970692,
                243540,
                232560,
                149153400,
                437400,
                16215,
                713460,
                75524400,
                118800,
                1575,
                106920,
                10150,
                13770000,
                33999966,
                177811200,
                64680,
                2880768,
                632459520,
                8675100,
                498700800,
                213572700,
                18657600,
                22,
                6993,
                49,
                177147000,
                6480,
                20,
                3910368,
                85201200,
                1764,
                120093120,
                16022160,
                290822400,
                6219200,
                29376000,
                235290,
                20979000,
                5,
                384,
                959140,
                443944800,
                11303040,
                952560,
                47736000,
                33404280,
                39936,
                11864320,
                144270720,
                12868224,
                18289152,
                87230682,
                145860,
                262548,
                10276500,
                12,
                612,
                179010000,
                622987200,
                108475200,
                1012,
                60,
                14880,
                10924200,
                2285568,
                149178000,
                1573936,
                195695500,
                213269760,
                24975,
                12000,
                3706560,
                168382080,
                114724,
                87650640,
                8019000,
                8035200,
                8621844,
                514500,
                155,
                132612480,
                1676700,
                627318720,
                39330,
                17,
                926100000,
                283360,
                69949440,
                856575,
                4092,
                130,
                720,
                958035000,
                5396820,
                2668,
                6606336,
                169708000,
                2352240,
                26,
                40608000,
                324576,
                3220,
                4945920,
                187697664,
                350,
                3965520,
                40500,
                9000,
                142560,
                39580800,
                447051000,
                19077120,
                36605250,
                775,
                19404,
                87514000,
                2673,
                9720,
                4942080,
                56752500,
                118216665,
                858,
                18225,
                3124800,
                1530,
                380160,
                24554880,
                2762100,
                646945200,
                173210400,
                22376250,
                731076192,
                161,
                44705100,
                145981440,
                18223660,
                215424,
                878526000,
                22883952,
                92092,
                7306200,
                32,
                2708160,
                566957475,
                17305344,
                119556000,
                411402240,
                1292544,
                454480,
                2208,
                27498240,
                249230520,
                88058880,
                2108,
                527800,
                455,
                49846104,
                801900,
                252450,
                7644,
                129540320,
                2241675,
                1330,
                71089200,
                2709630,
                43545600,
                497250,
                4972968,
                826277760,
                249091200,
                68827500,
                60900,
                271282240,
                13910400,
                88609950,
                46189440,
                3088800,
                582912000,
                4284000,
                304980000,
                32736,
                992,
                52992,
                454545000,
                14064960,
                72967500,
                892584000,
                61678260,
                3410,
                49104000,
                840931520,
                107805600,
                200475,
                35384580,
                4289408,
                599079390,
                777,
                465696,
                7956000,
                540960,
                3385200,
                8741250,
                17748,
                2528240,
                2248480,
                83076840,
                366282000,
                15120000,
                6871956,
                15586560,
                992673792,
                367200,
                65577600,
                635796000,
                150,
                62524000,
                7551600,
                1716660,
                85932,
                209986560,
                6167826,
                1557192,
                20702500,
                157320,
                14427072,
                553402080,
                203290560,
                3830112,
                1500,
                120992256,
                89280,
                66943800,
                8937984,
                30,
                32457600,
                75140,
                874,
                34398000,
                390600,
                955500,
                32542560,
                51068160,
                6624,
                545368824,
                316461600,
                236670,
                598067712,
                97538400,
                3240000,
                664801200,
                6120,
                477487296,
                445419000,
                38318280,
                148800,
                7,
                1055600,
                9128700,
                6472800,
                13176240,
                535680,
                7998,
                345960,
                1262250,
                78693120,
                1364,
                15,
                13800,
                406000,
                42,
                23,
                703872,
                787939152,
                24288,
                37795758,
                6300000,
                145704960,
                124,
                46920,
                3142656,
                31725,
                92,
                186300,
                1470,
                73500,
                3495250,
                196416,
                639878400,
                65800,
                1015680,
                131176500,
                37264500,
                243984000,
                19227000,
                917280,
                9384000,
                81840,
                454406400,
                795217500,
                147420000,
                6976800,
                14651280,
                116,
                11960,
                153740160,
                799948800,
                5184000,
                501686640,
                1020,
                773500,
                145763550,
                26417664,
                11446380,
                13,
                14817600,
                406125720,
                7068600,
                730667520,
                3371004,
                2677752,
                2692305,
                70615314,
                1771,
                388411200,
                20175075,
                14742000,
                139991040,
                302400,
                40131360,
                21740796,
                5996025,
                205615179,
                469193472,
                23220,
                8286300,
                19706400,
                2812992,
                72886425,
                3072,
                6557760,
                551779200,
                960,
                74592,
                185427840,
                40068864,
                883872000,
                85250,
                3499200,
                2210,
                402772500,
                1274,
                106260,
                4392080,
                953146480,
                90744192,
                132699840,
                4270560,
                361746000,
                342720,
                673536600,
                2418,
                234600,
                967255800,
                34500,
                8910,
                196040,
                374190336,
                9790200,
                694747200,
                5385600,
                907200,
                493426080,
                804683880,
                13820544,
                7999488,
                4879680,
                88400,
                13765500,
                28,
                377,
                172339200,
                97152,
                427680,
                41731200,
                92610,
                13950000,
                564200,
                2520,
                74970,
                11603592,
                16,
                18200,
                201386250,
                474525,
                531468,
                1860,
                51840,
                677376,
                59520,
                4457400,
                8912376,
                6742008,
                11013975,
                566280,
                330832,
                110707200,
                172727100,
                382200,
                942480,
                10200,
                3210480,
                2033600,
                11289564,
                6667920,
                675347400,
                79994880,
                27676800,
                158100,
                133722000,
                66769920,
                332041248,
                25,
                1545600,
                21450,
                655966080,
                11814660,
                223200,
                4151040,
                1016064,
                35,
                1607040,
                924,
                586333020,
                174787200,
                63756,
                18957120,
                788900000,
                351900000,
                1380,
                5441800,
                374,
                44200,
                38640,
                8307684,
                109707264,
                2178,
                7440,
                6577200,
                29435,
                264600000,
                12960000,
                2646,
                891691416,
                475656192,
                214033920,
                431708160,
                70340256,
                404736,
                39104,
                787059000,
                3208500,
                220103100,
                191268,
                66960000,
                18500832,
                856016640,
                173901000,
                1238688,
                157489920,
                54782,
                550946880,
                242573760,
                257040,
                282720,
                117645000,
                165369600,
                13110,
                434079360,
                9133344,
                621000,
                174037500,
                126960,
                6147900,
                137491200,
                29559600,
                700,
                185220000,
                317520000,
                200344320,
                14036,
                26601120,
                3535488,
                3649940,
                16240,
                61659000,
                430848,
                779483250,
                363528000,
                419764800,
                729933750,
                386661600,
                111481920,
                35700,
                6561000,
                68695200,
                70,
                297,
                83700,
                990,
                113076810,
                461538,
                787529952,
                4324,
                20727,
                40350150,
                218700,
                846720,
                540,
                29889000,
                1016600,
                277704000,
                62734080,
                14856192,
                210924000,
                589248000,
                5760,
                222393600,
                30180600,
                166059400,
                31021056,
                98208,
                21,
                21168,
                98208000,
                13464,
                1555200,
                16077600,
                288,
                4332042,
                320550912,
                204989400,
                785664,
                67897440,
                65472,
                16228800,
                70560,
                80352,
                8,
                9520896,
                71280,
                4862,
                44,
                12545280,
                657395200,
                39,
                64152000,
                283719996,
                247443840,
                924159600,
                20286000,
                268065,
                138983850,
                9300,
                5286120,
                61534200,
                496601280,
                875033280,
                6370,
                5940,
                364,
                29412,
                261360,
                1248,
                477290880,
                5880,
                669600,
                82174400,
                53568,
                483000,
                36,
                18,
                29728512,
                12057760,
                3046680,
                44660,
                368874000,
                167040,
                4276800,
                83462400,
                11050,
                638,
                34300000,
                27,
                509110272,
                437132430,
                81200,
                33,
                6277500,
                113601600,
                14850,
                10789200,
                157216500,
                20348928,
                10701900,
                365904000,
                1728,
                1782960,
                1255800,
                38321400,
                3542,
                6229872,
                40864824,
                514483200,
                43,
                1159200,
                413100,
                1127100,
                8019,
                198251550,
                47,
                30950400,
                2115,
                46,
                45900,
                233280000,
                125736,
                200508,
                5742,
                222456,
                442520,
                245188944,
                162288000,
                5589000,
                76923,
                2461536,
                415457280,
                715936320,
                179289600,
                14826240,
                17150000,
                13759200,
                63240,
                7001280,
                663000,
                22776600,
                221925825,
                920700,
                1421000,
                1715616,
                30198960,
                1766100,
                2480,
                290,
                460,
                1556640,
                1015,
                145411200,
                11350500,
                824199480,
                539028000,
                11865150,
                882000,
                19,
                830297000,
                159840,
                7632800,
                81053840,
                68250,
                77873400,
                123965952,
                164826900,
                23040,
                347200,
                51323580,
                30294000,
                140777000,
                1023,
                147556500,
                273420,
                13665960,
                2760,
                21780,
                77552640,
                3245760,
                341433225,
                930,
                12740,
                441,
                960498,
                184988160,
                219240000,
                125854344,
                13986,
                174960,
                53978400,
                2163168,
                456840000,
                1513400,
                179676000,
                90810720,
                28569600,
                4923072,
                807003000,
                49758720,
                47404500,
                480,
                42340320,
                837000000,
                3,
                3720,
                15847920,
                1400,
                1715000,
                251160,
                198,
                504708750,
                8932000,
                6311250,
                1458240,
                96,
                37235712,
                911400,
                255816,
                142084800,
                39346560,
                2384640,
                38491200,
                1872000,
                899640,
                14586,
                294624,
                37,
                239760,
                469476000,
                1015200,
                531454000,
                411840,
                36352800,
                15367680,
                273454272,
                63987840,
                22416750,
                24500,
                171535,
                683384832,
                47586240,
                82800,
                112266,
                12746370,
                429545025,
                875769840,
                125468160,
                74,
                39412800,
                45904320,
                9313920,
                1589760,
                24,
                570240,
                72912000,
                107880,
                1758120,
                7980,
                2614640,
                34,
                12987000,
                3124044,
                728640,
                21420,
                4,
                22855680,
                21600,
                99,
                11,
                203076720,
                90132,
                687447000,
                5049000,
                747225,
                37620,
                13363200,
                209265525,
                171169600,
                461039040,
                36946,
                79197560,
                35280,
                108100,
                22032000,
                343062720,
                29141775,
                906782240,
                297600,
                298378080,
                486129600,
                979104000,
                22151360,
                74576700,
                1647030,
                58870,
                828100,
                1064,
                58605120,
                12182400,
                860288,
                41,
                62107500,
                9,
                310495680,
                71951360,
                29,
                105995232,
                13838,
                1617000,
                832431600,
                328671,
                510,
                3826550,
                689018400,
                10959300,
                48,
                3294060,
                22720320,
                132022800,
                24663600,
                40,
                520,
                6756750,
                429624000,
                79497600,
                11427840,
                489167910,
                54734592,
                10847520,
                887284800,
                223948800,
                735139125,
                3478200,
                470235,
                649152000,
                86619456,
                932536800,
                2976,
                675,
                491756100,
                73780,
                1142784,
                5488560,
                1473780,
                301693392,
                8819902,
                88357500,
                40392,
                579600,
                457113600,
                2,
                692841600,
                77189112,
                49538412,
                18086640,
                104976000,
                35162400,
                4320,
                435,
                107892000,
                14,
                832,
                257094000,
                345,
                323389440,
                813440,
                13392000,
                29760,
                8391600,
                599400,
                1713600,
                154560,
                7380480,
                127429200,
                198360,
                8625,
                459345600,
                13117650,
                1309440,
                85680,
                41972175,
                75710880,
                87339648,
                55296000,
                1054,
                10098,
                269414640,
                787644000,
                34560,
                253,
                721353600,
                28072,
                5984,
                148764,
                84630,
                25966080,
                141120,
                46368,
                101680,
                31,
                82197720,
                3312400,
                2980800,
                18247680,
                12453120,
                9108,
                3050400,
            ],
            874417692,
        ],
    ]
    for executor in executors:
        start = timeit.default_timer()
        for _ in range(1):
            for n, t in enumerate(tests):
                sol = executor()
                result = sol.numFactoredBinaryTrees(t[0])
                exp = t[1]
                assert result == exp, (
                    f"\033[93m» {result} <> {exp}\033[91m for "
                    + f"test {n} using \033[1m{executor.__name__}"
                )
        stop = timeit.default_timer()
        used = str(round(stop - start, 5))
        cols = "{0:20}{1:10}{2:10}"
        res = cols.format(executor.__name__, used, "seconds")
        print(f"\033[92m» {res}\033[0m")


test()