Perfect Rice Bags

Question

Given a list of ricebags, choose a set of perfect ricebags with maximum size. A perfect ricebag set obeys the following conditions:

1. Atleast size of 2
2. When sorted, ricebags[i] * ricebags[i]=ricebags[i+1] , for all 0 <= i <= N(length of ricebags)

Example: ricebags = [3, 4, 2, 9, 16]
Possible sets are:

1. [3,9] -> size=2
2. [4,2] -> size=2
3. [4,16] -> size=2
4. [4,2,16] -> size=3

Answer = 3 (max-set-size)

Answer

The solution is very similar to Longest Consecutive Sequence

from typing import *
import math

def maxSetSize(riceBags: int):
    uniqueBags = set(riceBags)
    maxSize = 1

    for bag in riceBags:
        if not isStartNumber(bag, uniqueBags): continue

        currBag = bag
        length = 0

        while currBag in uniqueBags:
            currBag *= currBag
            length += 1
    
        maxSize = max(length, maxSize)

    return maxSize

    
def isStartNumber(num: int, uniqueBags: Set[int]):
    return not math.sqrt(num) in uniqueBags

Time complexity: $O(n)$
Space complexity: $O(n)$