Fancy Sequence

This page explains Java solution to problem Fancy Sequence using Math.

Problem Statement

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

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

Solution

package com.vc.hard;

import java.util.*;

class FancySequence {
    private long totalAddValue = 0;
    private long totalMultValue = 1;
    private List<Integer> numbers;

    long MOD = (int)1e9 + 7;

    public FancySequence() {
        numbers = new ArrayList<>();
    }

    public void append(int val) {
        long removeAddValue = (val - totalAddValue + MOD) % MOD;
        long removeMultValue = inverse(totalMultValue) % MOD;
        long newValue = (removeAddValue * removeMultValue) % MOD;
        numbers.add((int)newValue);
    }

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

    public void multAll(int m) {
        totalAddValue = (totalAddValue * m) % MOD;
        totalMultValue = (totalMultValue * m) % MOD;
    }

    public int getIndex(int index) {
        if(index < 0 || index >= numbers.size()) return -1;

        long ax = (numbers.get(index) * totalMultValue) % MOD;
        long b = (ax + totalAddValue) % MOD;
        return (int)b;
    }

    private long inverse(long x) {
        return power(x, MOD - 2);
    }

    private long power(long x, long y) {
        if(y == 0) return 1;

        long p = power(x, y / 2) % MOD;
        p = (p * p) % MOD;

        return y % 2 == 0 ? p : (p * x) % MOD;
    }
}

/**
 * Your Fancy object will be instantiated and called as such:
 * Fancy obj = new Fancy();
 * obj.append(val);
 * obj.addAll(inc);
 * obj.multAll(m);
 * int param_4 = obj.getIndex(idx);
 */

Time Complexity

append() takes O(log MOD)
addAll(inc) takes O(1)
multAll(inc) takes O(1)
getIndex(inc) takes O(1) Where
MOD is 10⁹ + 7

Space Complexity

O(N) Where
N is total number elements in Fancy Sequence