Skip to main content

Fancy Sequence

Problem​

Write an API that generates fancy sequences using the appendappend, addAlladdAll, and multAllmultAll operations.

Implement the FancyFancy 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 idxidx (0-indexed) of the sequence modulo 10910^9 + 77. If the index is greater or equal than the length of the sequence, return −1-1.

Examples​

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 <= 10^5
  • At most 10510^5 calls total will be made to appendappend, addAlladdAll, multAllmultAll, and getIndexgetIndex.

Approach​

To solve the problem, we need to understand the nature of the allowed moves:

  1. Using Lazy Operations:

    • Instead of updating the entire sequence for addAlladdAll and multAllmultAll, we maintain cumulative addition and multiplication factors. This way, we can defer the actual updates to when we need to access a particular element.
  2. Tracking Inverse Operations:

    • When appending a new value, we need to account for the current cumulative operations, so we store values in a form that can be easily adjusted when retrieving them.
  3. Efficient Index Retrieval:

    • By maintaining cumulative operations and only applying them when accessing an index, we ensure that our operations are efficient and avoid unnecessary updates to the sequence.

Solution for Fancy Sequence​

The problem involves three types of operations on a sequence of numbers: appending a value, adding a value to all elements, and multiplying all elements by a value. A naive approach would directly modify the sequence for each operation, but this would be inefficient given the constraints. Instead, we can use lazy propagation-like techniques to efficiently handle the operations.

Code in Java​

import java.util.ArrayList;
import java.util.List;

class Fancy {
private static final int MOD = 1000000007;
private List<Long> sequence;
private long add;
private long mult;

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

public void append(int val) {
// Apply the inverse of the current add and mult to keep the value as its original form
long adjustedVal = ((val - add) * modInverse(mult, MOD)) % MOD;
if (adjustedVal < 0) adjustedVal += MOD;
sequence.add(adjustedVal);
}

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

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

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

// Function to compute the modular inverse using Fermat's Little Theorem
private long modInverse(long a, int mod) {
return power(a, mod - 2, mod);
}

// Function to compute (x^y) % mod
private long power(long x, int y, int mod) {
if (y == 0) return 1;
long p = power(x, y / 2, mod) % mod;
p = (p * p) % mod;
return (y % 2 == 0) ? p : (x * p) % mod;
}

public static void main(String[] args) {
Fancy fancy = new Fancy();
fancy.append(2);
fancy.addAll(3);
fancy.append(7);
fancy.multAll(2);
System.out.println(fancy.getIndex(0));
fancy.addAll(3);
fancy.append(10);
fancy.multAll(2);
System.out.println(fancy.getIndex(0));
System.out.println(fancy.getIndex(1));
System.out.println(fancy.getIndex(2));
}
}

Complexity Analysis​

Time Complexity: O(1)O(1)​

Reason: Time Complexity is O(1)O(1), because append involves adding an element to the list, Whereas addAll only updates a cumulative variable, multAll updates cumulative variables and lastly getIndex, it basically involves getIndex calculating the result using the cumulative variables.

Space Complexity: O(n)O(n)​

Reason: O(n)O(n), where n is the number of elements in the sequence, as we store each element.

References