LeetCode Solutions Blog

Fancy Sequence

Difficulty: Hard

Problem Description

Implement the Fancy class that generates fancy sequences with operations to append integers, increment all values, multiply all values, and retrieve the value at a specific index modulo 10^9 + 7.

Key Insights

Maintain a list to store the sequence of integers.
Use two variables to track the total increment and multiplier applied to all elements.
When retrieving the value at a specific index, compute the effective value using the stored increment and multiplier to avoid modifying all elements directly.

Space and Time Complexity

Time Complexity:

O(1) for append, addAll, and multAll operations.
O(1) for getIndex, as it computes the value in constant time.

Space Complexity:

O(n) for storing the sequence of integers.

Solution

The solution uses a list to store the integers of the sequence. The class maintains two variables: total_increment for the cumulative increment applied and total_multiplier for the cumulative multiplier. This allows operations to be performed efficiently without updating the entire list of integers directly. The getIndex method computes the effective value using these two variables, ensuring the correct result is returned even after multiple operations.

Code Solutions

class Fancy:
    def __init__(self):
        self.sequence = []  # List to store the elements
        self.total_increment = 0  # Total increment applied to all elements
        self.total_multiplier = 1  # Total multiplier applied to all elements

    def append(self, val: int) -> None:
        # Adjust the value to account for the total increment and multiplier
        adjusted_val = (val - self.total_increment) * pow(self.total_multiplier, MOD - 2, MOD) % MOD
        self.sequence.append(adjusted_val)

    def addAll(self, inc: int) -> None:
        self.total_increment += inc  # Update the total increment

    def multAll(self, m: int) -> None:
        self.total_increment *= m  # Update the total increment
        self.total_multiplier *= m  # Update the total multiplier

    def getIndex(self, idx: int) -> int:
        if idx >= len(self.sequence):
            return -1  # Index out of bounds
        # Calculate the current value at the index considering increments and multipliers
        adjusted_value = (self.sequence[idx] * self.total_multiplier + self.total_increment) % MOD
        return adjusted_value

MOD = 10**9 + 7