LeetCode 1622: Fancy Sequence

Explanation

To implement the Fancy class, we can maintain two lists: one for the actual sequence and one for the operations to apply on the sequence. We will also need to keep track of the total multiplication and addition factors applied to the sequence. When getting the value at a specific index, we can calculate it based on the original value at that index, and the cumulative multiplication and addition factors.

Algorithm:

1. Initialize the Fancy class with empty lists for the sequence and operations, and set multiplication and addition factors to 1 and 0 respectively.
2. Implement append(val) to add the value to the sequence.
3. Implement addAll(inc) to append the increment operation to the operations list.
4. Implement multAll(m) to append the multiplication operation to the operations list.
5. Implement getIndex(idx) to calculate the value at index idx based on the original value, multiplication factor, and addition factor.

Time Complexity:

• Append, addAll, and multAll operations run in O(1) time complexity.
• getIndex operation runs in O(1) time complexity.

Space Complexity:

• O(N) where N is the number of elements in the sequence.

class Fancy {
    List<Long> seq;
    List<Long> addOps;
    List<Long> multOps;
    long addFactor;
    long multFactor;
    long MOD = 1000000007;

    public Fancy() {
        seq = new ArrayList<>();
        addOps = new ArrayList<>();
        multOps = new ArrayList<>();
        addFactor = 0;
        multFactor = 1;
    }

    public void append(int val) {
        seq.add((val - addFactor + MOD) % MOD * pow(multFactor, MOD - 2) % MOD);
    }

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

    public void multAll(int m) {
        addFactor = (addFactor * m) % MOD;
        multFactor = (multFactor * m) % MOD;
    }

    public int getIndex(int idx) {
        if (idx >= seq.size()) {
            return -1;
        }
        return (int) ((seq.get(idx) * multFactor + addFactor) % MOD);
    }

    private long pow(long x, long y) {
        long ans = 1;
        while (y > 0) {
            if (y % 2 == 1) {
                ans = (ans * x) % MOD;
            }
            x = (x * x) % MOD;
            y /= 2;
        }
        return ans;
    }
}