Tushar’s Birthday Bombs

• Time : $O(n)$
• Space : $O(n)$

vector<int> Solution::solve(int A, vector<int> &B) {
    int mi = INT_MAX;
    vector<int> cand;
    unordered_map<int, int> mp;

    for(int i = 0; i < B.size(); i++) {
        if(B[i] < mi) {
            mi = B[i];
            cand.push_back(B[i]);
            mp[B[i]] = i;
        }
    }
    
    vector<int> res;
    for(auto c : cand) {
        while(c <= A) {
            int now = A - c;
            int ma = A / mi;
            if(1 + now / mi == ma) {
                res.push_back(mp[c]);
                A -= c;
            } else break;
        }
    }

    return res;
}