Leetcode 1622 Fancy Sequence Solution in Java | Hindi Coding Community

 

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.

Java Code :

class Fancy {

private ArrayList<Long> lst;

private ArrayList<Long> add;

private ArrayList<Long> mult;

private final long MOD = 1000000007;

public Fancy() {

lst = new ArrayList<>();

add = new ArrayList<>();

mult = new ArrayList<>();

add.add(0L);

mult.add(1L);

}

public void append(int val) {

lst.add((long) val);

int l = add.size();

add.add(add.get(l - 1));

mult.add(mult.get(l - 1));

}

public void addAll(int inc) {

int l = add.size();

add.set(l - 1, add.get(l - 1) + inc);

}

public void multAll(int m) {

int l = add.size();

add.set(l - 1, (add.get(l - 1) * m) % MOD);

mult.set(l - 1, (mult.get(l - 1) * m) % MOD);

}

public int getIndex(int idx) {

if (idx >= lst.size()) return -1;

int l = add.size();

long m = (mult.get(l - 1) * inverse(mult.get(idx))) % MOD;

long a = (add.get(l - 1) - (add.get(idx) * m) % MOD + MOD) % MOD;

return (int) (((lst.get(idx) * m) % MOD + a) % MOD);

}

long inverse(long a) {

return pow(a, MOD - 2);

}

long pow(long a, long n) {

if (n == 0) return 1;

if (n % 2 == 0) {

long t = pow(a, n / 2);

return (t * t) % MOD;

} else {

return (pow(a, n - 1) * a) % MOD;

}

}

}