LeetCode 1622: Fancy Sequence Solution

Master LeetCode problem 1622 (Fancy Sequence), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1622. Fancy Sequence

Hard

Math Design Segment Tree

Problem Explanation

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:

Initialize the Fancy class with empty lists for the sequence and operations, and set multiplication and addition factors to 1 and 0 respectively.
Implement append(val) to add the value to the sequence.
Implement addAll(inc) to append the increment operation to the operations list.
Implement multAll(m) to append the multiplication operation to the operations list.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1622 (Fancy Sequence)?

This page provides optimized solutions for LeetCode problem 1622 (Fancy Sequence) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1622 (Fancy Sequence)?

The time complexity for LeetCode 1622 (Fancy Sequence) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1622 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1622 in Java, C++, or Python.

Back to LeetCode Solutions