In this guide, you will get 1622. Fancy Sequence LeetCode Solution with the best time and space complexity. The solution to Fancy Sequence problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
1 <= val, inc, m <= 100
0 <= idx <= 105
At most 105 calls total will be made to append, addAll, multAll, and getIndex.
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(|\texttt{append()}|)
1622. Fancy Sequence LeetCode Solution in C++
class Fancy {
public:
// To undo a * val + b and get the original value, we append (val - b) / a.
// By Fermat's little theorem:
// a^(p - 1) ≡ 1 (mod p)
// a^(p - 2) ≡ a^(-1) (mod p)
// So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p)
void append(int val) {
const long x = (val - b + kMod) % kMod;
vals.push_back(x * modPow(a, kMod - 2) % kMod);
}
// If the value is a * val + b, then the value after adding by `inc` will be
// a * val + b + inc. So, we adjust b to b + inc.
void addAll(int inc) {
b = (b + inc) % kMod;
}
// If the value is a * val + b, then the value after multiplying by `m` will
// be a * m * val + b * m. So, we adjust a to a * m and b to b * m.
void multAll(int m) {
a = (a * m) % kMod;
b = (b * m) % kMod;
}
int getIndex(int idx) {
return idx >= vals.size() ? -1 : (a * vals[idx] + b) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
// For each `val` in `vals`, it actually represents a * val + b.
vector<unsigned long> vals;
unsigned long a = 1;
unsigned long b = 0;
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
1622. Fancy Sequence LeetCode Solution in Java
class Fancy {
// To undo a * val + b and get the original value, we append (val - b) / a.
// By Fermat's little theorem:
// a^(p - 1) ≡ 1 (mod p)
// a^(p - 2) ≡ a^(-1) (mod p)
// So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p)
public void append(int val) {
final long x = (val - b + kMod) % kMod;
vals.add(x * modPow(a, kMod - 2) % kMod);
}
// If the value is a * val + b, then the value after adding by `inc` will be
// a * val + b + inc. So, we adjust b to b + inc.
public void addAll(int inc) {
b = (b + inc) % kMod;
}
// If the value is a * val + b, then the value after multiplying by `m` will
// be a * m * val + b * m. So, we adjust a to a * m and b to b * m.
public void multAll(int m) {
a = (a * m) % kMod;
b = (b * m) % kMod;
}
public int getIndex(int idx) {
return idx >= vals.size() ? -1 : (int) ((a * vals.get(idx) + b) % kMod);
}
private static final int kMod = 1_000_000_007;
// For each `val` in `vals`, it actually represents a * val + b.
private List<Long> vals = new ArrayList<>();
private long a = 1;
private long b = 0;
private int modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return (int) (x * modPow(x % kMod, (n - 1)) % kMod);
return modPow(x * x % kMod, (n / 2)) % kMod;
}
} // code provided by PROGIEZ
1622. Fancy Sequence LeetCode Solution in Python
class Fancy:
def __init__(self):
self.kMod = 1_000_000_007
# For each `val` in `vals`, it actually represents a * val + b.
self.vals = []
self.a = 1
self.b = 0
# To undo a * val + b and get the original value, we append (val - b) // a.
# By Fermat's little theorem:
# a^(p - 1) ≡ 1 (mod p)
# a^(p - 2) ≡ a^(-1) (mod p)
# So, (val - b) / a ≡ (val - b) * a^(p - 2) (mod p)
def append(self, val: int) -> None:
x = (val - self.b + self.kMod) % self.kMod
self.vals.append(x * pow(self.a, self.kMod - 2, self.kMod))
# If the value is a * val + b, then the value after adding by `inc` will be
# a * val + b + inc. So, we adjust b to b + inc.
def addAll(self, inc: int) -> None:
self.b = (self.b + inc) % self.kMod
# If the value is a * val + b, then the value after multiplying by `m` will
# be a * m * val + b * m. So, we adjust a to a * m and b to b * m.
def multAll(self, m: int) -> None:
self.a = (self.a * m) % self.kMod
self.b = (self.b * m) % self.kMod
def getIndex(self, idx: int) -> int:
return (-1 if idx >= len(self.vals)
else (self.a * self.vals[idx] + self.b) % self.kMod) # code by PROGIEZ
