Quant Memo
Coding/●●●●●

Design a stack that reports the GCD of its elements

You are tracking the lot sizes of the orders currently resting and want the largest unit they all divide into: the greatest common divisor of everything in the stack. Orders push and pop, and get_gcd should stay O(1)O(1).

s = GcdStack()
s.push(12); s.push(18); s.push(30)
s.get_gcd() -> 6          # gcd(12, 18, 30)
s.pop()                   # removes 30
s.get_gcd() -> 6          # gcd(12, 18)
s.pop()                   # removes 18
s.get_gcd() -> 12         # gcd(12)

Design push, pop, and get_gcd with every operation in O(1)O(1) (treating gcd of two numbers as a constant-time primitive).

Your answer

This one is open-ended. Work it through, then check your reasoning against the full solution.

More Coding questions