1622. Fancy Sequence

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.

# OJ: https://leetcode.com/problems/fancy-sequence/
# Author: github.com/lzl124631x
# 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/
// Author: github.com/lzl124631x
// 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;
    }
};