Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1622.html

1622. Fancy Sequence (Hard)

Write an API that generates fancy sequences using the append, addAll, and multAll operations.

Implement the Fancy class:

  • Fancy() Initializes the object with an empty sequence.
  • void append(val) Appends an integer val to the end of the sequence.
  • void addAll(inc) Increments all existing values in the sequence by an integer inc.
  • void multAll(m) Multiplies all existing values in the sequence by an integer m.
  • int getIndex(idx) Gets the current value at index idx (0-indexed) of the sequence modulo 109 + 7. If the index is greater or equal than the length of the sequence, return -1.

 

Example 1:

Input
["Fancy", "append", "addAll", "append", "multAll", "getIndex", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"]
[[], [2], [3], [7], [2], [0], [3], [10], [2], [0], [1], [2]]
Output
[null, null, null, null, null, 10, null, null, null, 26, 34, 20]

Explanation
Fancy fancy = new Fancy();
fancy.append(2);   // fancy sequence: [2]
fancy.addAll(3);   // fancy sequence: [2+3] -> [5]
fancy.append(7);   // fancy sequence: [5, 7]
fancy.multAll(2);  // fancy sequence: [5*2, 7*2] -> [10, 14]
fancy.getIndex(0); // return 10
fancy.addAll(3);   // fancy sequence: [10+3, 14+3] -> [13, 17]
fancy.append(10);  // fancy sequence: [13, 17, 10]
fancy.multAll(2);  // fancy sequence: [13*2, 17*2, 10*2] -> [26, 34, 20]
fancy.getIndex(0); // return 26
fancy.getIndex(1); // return 34
fancy.getIndex(2); // return 20

 

Constraints:

  • 1 <= val, inc, m <= 100
  • 0 <= idx <= 105
  • At most 105 calls total will be made to append, addAll, multAll, and getIndex.

Related Topics:
Math, Design

Solution 1.

MOD = int(1e9 + 7)


class Node:
    def __init__(self, l, r):
        self.left = None
        self.right = None
        self.l = l
        self.r = r
        self.mid = (l + r) >> 1
        self.v = 0
        self.add = 0
        self.mul = 1


class SegmentTree:
    def __init__(self):
        self.root = Node(1, int(1e5 + 1))

    def modifyAdd(self, l, r, inc, node=None):
        if l > r:
            return
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            node.v = (node.v + (node.r - node.l + 1) * inc) % MOD
            node.add += inc
            return
        self.pushdown(node)
        if l <= node.mid:
            self.modifyAdd(l, r, inc, node.left)
        if r > node.mid:
            self.modifyAdd(l, r, inc, node.right)
        self.pushup(node)

    def modifyMul(self, l, r, m, node=None):
        if l > r:
            return
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            node.v = (node.v * m) % MOD
            node.add = (node.add * m) % MOD
            node.mul = (node.mul * m) % MOD
            return
        self.pushdown(node)
        if l <= node.mid:
            self.modifyMul(l, r, m, node.left)
        if r > node.mid:
            self.modifyMul(l, r, m, node.right)
        self.pushup(node)

    def query(self, l, r, node=None):
        if l > r:
            return 0
        if node is None:
            node = self.root
        if node.l >= l and node.r <= r:
            return node.v
        self.pushdown(node)
        v = 0
        if l <= node.mid:
            v = (v + self.query(l, r, node.left)) % MOD
        if r > node.mid:
            v = (v + self.query(l, r, node.right)) % MOD
        return v

    def pushup(self, node):
        node.v = (node.left.v + node.right.v) % MOD

    def pushdown(self, node):
        if node.left is None:
            node.left = Node(node.l, node.mid)
        if node.right is None:
            node.right = Node(node.mid + 1, node.r)
        left, right = node.left, node.right
        if node.add != 0 or node.mul != 1:
            left.v = (left.v * node.mul + (left.r - left.l + 1) * node.add) % MOD
            right.v = (right.v * node.mul + (right.r - right.l + 1) * node.add) % MOD
            left.add = (left.add * node.mul + node.add) % MOD
            right.add = (right.add * node.mul + node.add) % MOD
            left.mul = (left.mul * node.mul) % MOD
            right.mul = (right.mul * node.mul) % MOD
            node.add = 0
            node.mul = 1


class Fancy:
    def __init__(self):
        self.n = 0
        self.tree = SegmentTree()

    def append(self, val: int) -> None:
        self.n += 1
        self.tree.modifyAdd(self.n, self.n, val)

    def addAll(self, inc: int) -> None:
        self.tree.modifyAdd(1, self.n, inc)

    def multAll(self, m: int) -> None:
        self.tree.modifyMul(1, self.n, m)

    def getIndex(self, idx: int) -> int:
        return -1 if idx >= self.n else self.tree.query(idx + 1, idx + 1)


# Your Fancy object will be instantiated and called as such:
# obj = Fancy()
# obj.append(val)
# obj.addAll(inc)
# obj.multAll(m)
# param_4 = obj.getIndex(idx)

############

# OJ: https://leetcode.com/problems/fancy-sequence/

# Time: O(1) for all
# Space: O(N)
# Ref: https://leetcode.com/problems/fancy-sequence/discuss/898753/Python-Time-O(1)-for-each
class Fancy:
    def __init__(self):
        self.A = []
        self.add = [0]
        self.mul = [1]
    def append(self, val: int) -> None:
        self.A.append(val)
        self.add.append(self.add[-1])
        self.mul.append(self.mul[-1])
    def addAll(self, inc: int) -> None:
        self.add[-1] += inc
    def multAll(self, m: int) -> None:
        self.add[-1] *= m
        self.mul[-1] *= m
    def getIndex(self, i: int) -> int:
        if i >= len(self.A): return -1
        m = self.mul[-1] // self.mul[i]
        inc = self.add[-1] - self.add[i] * m
        return int((self.A[i] * m + inc) % (10 ** 9 + 7))

Solution 2.

// OJ: https://leetcode.com/problems/fancy-sequence/
// Time: O(1) for all
// Space: O(N)
// Ref: https://leetcode.com/problems/fancy-sequence/discuss/898861/C%2B%2B-Math-Solution-O(1)-extra-space-and-O(1)-time-for-each
class Fancy {
    typedef unsigned long UL;
    UL mod = 1e9 + 7, len = 0, increment = 0, mul = 1, A[100001];
    UL modPow(UL base, UL exp) {
        UL ans = 1, p = base;
        for (; exp; exp >>= 1) {
            if (exp & 1) ans = (ans * p) % mod;
            p = (p * p) % mod;
        }
        return ans;
    }
public:
    Fancy() {}
    void append(int val) {
        A[len++] = (((val - increment + mod) % mod) * modPow(mul, mod - 2)) % mod;
    }
    void addAll(int inc) {
        increment = (increment + inc) % mod;
    }
    void multAll(int m) {
        mul = (mul * m) % mod;
        increment = (increment * m) % mod;
    }
    int getIndex(int i) {
        return i >= len ? -1 : ((A[i] * mul) % mod + increment) % mod;
    }
};

All Problems

All Solutions