Array-Sum Operation

Question

I have written this code using vector. Some case has been passed but others show timeout termination error.

The problem statement is:-

You have an identity permutation of N integers as an array initially. An identity permutation of N integers is [1,2,3,...N-1,N]. In this task, you have to perform M operations on the array and report the sum of the elements of the array after each operation.

The i^th operation consists of an integer op_i.

If the array contains op_i, swap the first and last elements in the array. Else, remove the last element of the array and push op_i to the end of the array. Input Format

The first line contains two space-separated integers N and M. Then, M lines follow denoting the operations op_i.

Constraints :

2<=N,M <= 10^5

1 <= op <= 5*10^5

Output Format

Print M lines, each containing a single integer denoting the answer to each of the M operations.

Sample Input 0

3 2
4
2

Sample Output 0

7
7

Explanation 0

Initially, the array is [1,2,3].

After the 1st operation, the array becomes[1,2,4] as op_i = 4, as 4 is not present in the current array, we remove 3 and push 4 to the end of the array and hence, sum=7 .

After 2nd operation the array becomes [4,2,1] as op_i = 2, as 2 is present in the current array, we swap 1 and 4 and hence, sum=7.

Here is my code:

#include <bits/stdc++.h>

using namespace std;

 int main()

 {

    long int N,M,op,i,t=0;
    vector<long int > g1;
    cin>>N>>M;
    if(N>=2 && M>=2) {
    g1.reserve(N);
        for(i = 1;i<=N;i++) {
        g1.push_back(i);
    }
    while(M--) {

        cin>>op;
        auto it = find(g1.begin(), g1.end(), op);
            if(it != (g1.end())) {

                t = g1.front();
                g1.front() = g1.back();
                g1.back() = t;
                cout<<accumulate(g1.begin(), g1.end(), 0);
                cout<<endl;
            }
            else {

                g1.back() = op;
                cout<<accumulate(g1.begin(), g1.end(), 0);
                cout<<endl;
            }
            
        }
    }
    
    return 0;
}

Please Suggest changes.

Unrelated but important: [Why should I not `#include `?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) [Why is `using namespace std;` considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Evg, Aug 01 '20 at 09:09
Iterating the whole array for each query will be too slow. You should hold the sum and update thinking about the change of elements. To judge if a value is in the array, `std::map` or `std::set` will be useful. — MikeCAT, Aug 01 '20 at 09:15
`std::find` is linear in `N`, you have `M` iterations. The total running time will be at least `O(N*M)`. With an upper bound `10^5` for `N` and `M`, it is `10^10`. — Evg, Aug 01 '20 at 09:16
@OP -- Please note -- these questions from the online coding sites are designed so that naive, quadratic running-time solutions (such as yours) will exist for small input, but larger input will not work. You should realize this and take a note of this before writing any code to submit. — PaulMcKenzie, Aug 01 '20 at 09:43
From the continuous swapping and removal of array elements, I suggest you use a deque — kesarling He-Him, Aug 01 '20 at 10:43
@Nature, can u kindly provide the source or reference to this problem — Deepak Tatyaji Ahire, Aug 01 '20 at 12:08

score 0 · Answer 1 · answered Aug 01 '20 at 16:19

Looking carefully in question you will find that the operation are made only on the first and last element. So there is no need to involve a whole vector in it much less calculating the sum. we can calculate the whole sum of the elements except first and last by (n+1)(n-2)/2 and then we can manipulate the first and last element in the question. We can also shorten the search by using (1<op<n or op==first element or op == last element).

p.s. I am not sure it will work completely but it certainly is faster

score 0 · Answer 2 · edited Aug 01 '20 at 22:25

my guess, let take N = 3, op = [4, 2] N= [1,2,3] sum = ((N-2) * (N+1)) / 2, it leave first and last element, give the sum of numbers between them.

we need to play with the first and last elements. it's big o(n).

function performOperations(N, op) {
    let out = [];
    let first = 1, last = N;
    let sum = Math.ceil( ((N-2) * (N+1)) / 2);
    for(let i =0;i<op.length;i++){
        let not_between = !(op[i] >= 2 && op[i] <= N-1);
        if( first!= op[i] && last != op[i] && not_between) {
            last = op[i];
        }else {
            let t = first;
            first = last;
            last = t;
        }
        out.push(sum + first +last)
    }
    return out;
}

Array-Sum Operation

2 Answers2