We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Fancy Sequence

Number: 1728

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Design and implement a Fancy Sequence class that maintains a list of numbers with three update operations and one query operation. The API supports:

  • append(val): Append an integer val to the sequence.
  • addAll(inc): Add inc to every element in the sequence.
  • multAll(m): Multiply every element in the sequence by m.
  • getIndex(idx): Return the element at index idx (0-based) under modulo 10^9+7 transformation. If idx is out of bounds, return -1.

All operations must be efficient, even though multiple sequential transformations are applied across the sequence.

Key Insights

  • Instead of updating every element for addAll and multAll operations, maintain two global transformation parameters: a multiplicative factor and an additive offset.
  • For each appended element, record the current transformation state so that later adjustments can be computed relative to when the element was added.
  • For getIndex, use modular arithmetic along with the modular multiplicative inverse (Fermat’s little theorem) to “reverse” the effect of the transformation recorded at insertion.
  • This lazy propagation strategy allows each operation to run in O(1) time.

Space and Time Complexity

Time Complexity: O(1) per operation. Space Complexity: O(n), where n is the number of appended elements.

Solution

We maintain two global variables: prod (initially 1) and add (initially 0). Every time addAll(inc) or multAll(m) is called, we update these parameters to represent the cumulative effect of the operations on all elements. For each element appended, we record its value along with the state (prod, add) at the time of append. When getIndex(idx) is called, we “reverse” the transformation that was in place at append time by computing a ratio factor using the modular inverse. This lets us calculate the current value using the formula:

  result = (val * (globalProd / recordedProd) + (globalAdd – recordedAdd * (globalProd / recordedProd))) mod MOD

Modular arithmetic is used throughout to handle the modulo 10^9+7 requirement.

Code Solutions

# Define the Fancy class with required operations.
class Fancy:
    mod = 10**9 + 7  # modulo constant

    def __init__(self):
        # Initialize global multiplicative and additive factors.
        self.prod = 1
        self.add = 0
        # Array to store tuples of (val, prod at append, add at append)
        self.arr = []

    def append(self, val: int) -> None:
        # Record the value along with the current transformation factors.
        self.arr.append((val, self.prod, self.add))

    def addAll(self, inc: int) -> None:
        # Increment the global additive factor.
        self.add = (self.add + inc) % Fancy.mod

    def multAll(self, m: int) -> None:
        # Multiply both global factors by m.
        self.prod = (self.prod * m) % Fancy.mod
        self.add = (self.add * m) % Fancy.mod

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.arr):
            return -1
        val, prod_i, add_i = self.arr[idx]
        # Compute ratio = current global prod / recorded prod using modular inverse.
        inv_prod = pow(prod_i, Fancy.mod - 2, Fancy.mod)
        ratio = (self.prod * inv_prod) % Fancy.mod
        # Calculate current value by reversing the recorded state effect.
        result = (val * ratio + (self.add - add_i * ratio)) % Fancy.mod
        return result

# Example usage:
# fancy = Fancy()
# fancy.append(2)
# fancy.addAll(3)
# fancy.append(7)
# fancy.multAll(2)
# print(fancy.getIndex(0))  # Expected output: 10
← Back to All Questions