Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

**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

Solution

Method 1 - Using List

The problem involves creating and maintaining a sequence with operations (append, addAll, and multAll) that modify the entire sequence efficiently. Directly applying the operations on all elements every time would result in a poor time complexity when the sequence becomes large. To optimise this process:

Key Observations

  1. Tracking Operations:
    • Instead of modifying every element for each operation, maintain values add and mult that track the cumulative additions and multiplications applied to all elements.
  2. Delayed Evaluation:
    • When getIndex(idx) is called, compute the value at the specific index lazily by applying the stored operations.
  3. Modulo (10^9 + 7):
    • Since operations may result in large numbers, ensure all calculations are done modulo 10^9 + 7.

Approach

  • Use a list seq to store the appended values.
  • Maintain two variables:
    • add for cumulative addition.
    • mult for cumulative multiplication (starting with 1).
  • Implement the methods as follows:
    • append(val): Append the val adjusted for the current mult and add.
    • addAll(inc): Increment the add variable.
    • multAll(m): Update mult, and adjust the add based on the multiplication.
    • getIndex(idx): Retrieve the value at idx using the stored operations, modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Fancy {

    private ArrayList<Long> seq;
    private long add;
    private long mult;
    private final int MOD = 1000000007;

    public Fancy() {
        seq = new ArrayList<>();
        add = 0;
        mult = 1;
    }

    public void append(int val) {
        seq.add(((val - add + MOD) * modInverse(mult)) % MOD);
    }

    public void addAll(int inc) {
        add = (add + inc) % MOD;
    }

    public void multAll(int m) {
        mult = (mult * m) % MOD;
        add = (add * m) % MOD;
    }

    public int getIndex(int idx) {
        if (idx >= seq.size()) return -1;
        long ans = (((seq.get(idx) * mult) % MOD) + add) % MOD;
        return (int) ans;
    }

    // Helper function to compute modular inverse using Fermat's Little Theorem
    private long modInverse(long x) {
        return pow(x, MOD - 2);
    }

    private long pow(long x, int y) {
        long res = 1;
        while (y > 0) {
            if ((y & 1) == 1) res = (res * x) % MOD;
            x = (x * x) % MOD;
            y >>= 1;
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Fancy:
    def __init__(self) -> None:
        self.seq: List[int] = []
        self.add: int = 0
        self.mult: int = 1
        self.MOD = 10**9 + 7
    
    def append(self, val: int) -> None:
        self.seq.append((val - self.add + self.MOD) * self._mod_inverse(self.mult) % self.MOD)
    
    def addAll(self, inc: int) -> None:
        self.add = (self.add + inc) % self.MOD
    
    def multAll(self, m: int) -> None:
        self.mult = (self.mult * m) % self.MOD
        self.add = (self.add * m) % self.MOD
    
    def getIndex(self, idx: int) -> int:
        if idx >= len(self.seq):
            return -1
        ans = (self.seq[idx] * self.mult % self.MOD + self.add) % self.MOD
        return ans
    
    def _mod_inverse(self, x: int) -> int:
        return self._pow(x, self.MOD - 2)
    
    def _pow(self, x: int, y: int) -> int:
        res = 1
        while y > 0:
            if y & 1:
                res = res * x % self.MOD
            x = x * x % self.MOD
            y >>= 1
        return res

Complexity

  • ⏰ Time complexity: O(1) for each operation
  • 🧺 Space complexity: O(n) where n is the number of appended elements in the sequence.