Fancy Sequence - Practice Coding Problems

Fancy Sequence - Problem

Design and implement a Fancy class that supports dynamic sequence operations:

Fancy() - Initializes the object with an empty sequence
append(val) - Appends an integer val to the end of the sequence
addAll(inc) - Increments all existing values in the sequence by integer inc
multAll(m) - Multiplies all existing values in the sequence by integer m
getIndex(idx) - Gets the current value at index idx (0-indexed) modulo 10⁹ + 7. Returns -1 if the index is greater than or equal to the sequence length

All operations must handle large numbers and return results modulo 10⁹ + 7.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["Fancy", "append", "addAll", "append", "multAll", "getIndex", "getIndex", "getIndex"], values = [null, 2, 3, 7, 2, 0, 1, 2]

› Output: [10, 14, -1]

💡 Note: append(2): [2], addAll(3): [5], append(7): [5,7], multAll(2): [10,14]. getIndex(0)=10, getIndex(1)=14, getIndex(2)=-1 (out of bounds)

Example 2 — Multiple Multiplications

$ Input: operations = ["Fancy", "append", "multAll", "getIndex", "multAll", "getIndex"], values = [null, 5, 2, 0, 3, 0]

› Output: [10, 30]

💡 Note: append(5): [5], multAll(2): [10], getIndex(0)=10, multAll(3): [30], getIndex(0)=30

Example 3 — Empty Sequence

$ Input: operations = ["Fancy", "getIndex"], values = [null, 0]

› Output: [-1]

💡 Note: getIndex(0) on empty sequence returns -1

Constraints

1 ≤ val, inc, m ≤ 100
0 ≤ idx ≤ 100
At most 10⁵ calls total to append, addAll, multAll, and getIndex
All values modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Input

Operations: append(2), addAll(3), append(7), multAll(2)

Process

Track transformations lazily without updating elements

Output

getIndex returns transformed values: [10, 14]

Key Takeaway

🎯 Key Insight: Instead of updating all elements individually, track cumulative transformations and apply them lazily during retrieval

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use lazy propagation by tracking cumulative transformations instead of updating individual elements. The optimal approach maintains global multiplier and adder values, storing each element with its transformation state at insertion time. Time: O(1) for all operations, Space: O(n) for storing elements.

Common Approaches

Approach	Time	Space	Notes
✓ Lazy Propagation - Transform Tracking	O(1)	O(n)	Track cumulative transformations instead of updating individual elements
Brute Force - Direct Updates	O(n)	O(n)	Update every element in the sequence for each addAll and multAll operation

Lazy Propagation - Transform Tracking — Algorithm Steps

Step 1: Maintain global mult and add values for all operations
Step 2: Store original values with their individual transformation states
Step 3: Apply accumulated transformations during getIndex calls

Visualization

Tap to expand

Step-by-Step Walkthrough

Track State

Store global multiplier and adder

Lazy Updates

Operations update global state only

On-Demand

Apply transformations during getIndex

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007LL
#define MAX_SIZE 100000

typedef struct {
    long long sequence[MAX_SIZE][3]; // [value, mult_when_added, add_when_added]
    int size;
    long long globalMult;
    long long globalAdd;
} Fancy;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp / 2;
        base = (base * base) % mod;
    }
    return result;
}

long long modInverse(long long a) {
    return power(a, MOD - 2, MOD);
}

Fancy* fancyCreate() {
    Fancy* obj = (Fancy*)malloc(sizeof(Fancy));
    obj->size = 0;
    obj->globalMult = 1;
    obj->globalAdd = 0;
    return obj;
}

void fancyAppend(Fancy* obj, int val) {
    obj->sequence[obj->size][0] = val % MOD;
    obj->sequence[obj->size][1] = obj->globalMult;
    obj->sequence[obj->size][2] = obj->globalAdd;
    obj->size++;
}

void fancyAddAll(Fancy* obj, int inc) {
    obj->globalAdd = (obj->globalAdd + inc) % MOD;
}

void fancyMultAll(Fancy* obj, int m) {
    obj->globalMult = (obj->globalMult * m) % MOD;
    obj->globalAdd = (obj->globalAdd * m) % MOD;
}

int fancyGetIndex(Fancy* obj, int idx) {
    if (idx >= obj->size) {
        return -1;
    }
    
    long long val = obj->sequence[idx][0];
    long long multAtTime = obj->sequence[idx][1];
    long long addAtTime = obj->sequence[idx][2];
    
    long long multFactor = (obj->globalMult * modInverse(multAtTime)) % MOD;
    long long addFactor = (obj->globalAdd - (addAtTime * multFactor) % MOD + MOD) % MOD;
    addFactor = (addFactor * modInverse(multAtTime)) % MOD;
    
    long long result = (val * multFactor + addFactor) % MOD;
    return (int)result;
}

int main() {
    // For simplicity, assuming predefined test case
    Fancy* fancy = fancyCreate();
    
    fancyAppend(fancy, 2);
    fancyAddAll(fancy, 3);
    fancyAppend(fancy, 7);
    fancyMultAll(fancy, 2);
    
    printf("[%d,%d]\n", 
           fancyGetIndex(fancy, 0),
           fancyGetIndex(fancy, 1));
    
    free(fancy);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

All operations except getIndex are O(1), getIndex applies transformations in constant time

✓ Linear Growth

Space Complexity

O(n)

Store original values plus transformation state for each element

⚡ Linearithmic Space

15.4K Views

Medium Frequency

~35 min Avg. Time

278 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Lazy Propagation - Transform Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler