C++ Array manipulation

Question

Hey guys this is the question's link from hackerrank hackerrank problem

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long int sizeArr, operation;
    cin>>sizeArr>>operation;
    long int array[sizeArr];
    for(long int i=0;i<sizeArr;i++)
        array[i]=0;
    for(long int i=0;i<operation;i++)
    {
        long int a,b,k;
        cin>>a>>b>>k;
        for(long int j=a-1;j<=b-1;j++)
            array[j]+=k;
    }
    sort(array,array+sizeArr);
    cout<<array[sizeArr-1];
}

I coded it like this and the another person code it like

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    long int N,M,a,b,k,i,j,max=0,x=0;
    cin>>N>>M;
    long int *Arr = new long int[N+1]();
    for(i=0;i<M;i++)
    {
        cin>>a>>b>>k;
        Arr[a]+=k;            
        if((b+1)<=N) Arr[b+1]-=k;
    }
    for(i=1;i<=N;i++)
    {
       x=x+Arr[i];
       if(max<x) max=x;

    }
    cout<<max;
    return 0;
}

Mine one didn't clear all the test cases but the second one's code did. Any suggestions.

your code is wrong the other produces correct output? What is your question? — 463035818_is_not_an_ai, Dec 04 '20 at 08:48
First uses VLA extension (so no standard C++), second leaks memory... — Jarod42, Dec 04 '20 at 08:57
see here: [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard) — 463035818_is_not_an_ai, Dec 04 '20 at 08:59
Note that the other code is much more efficient: O(n + op), if op is the number of operations. You may have a time limit issue — Damien, Dec 04 '20 at 10:56

Akis Lionis · Answer 1 · 2020-12-04T09:53:34.433

0

The problem is that your colleague has this if((b+1)<=N) Arr[b+1]-=k; which means he sometimes subtracts but in your code, you only add in here array[j]+=k;.
And also your while function has a bigger range than your colleague (for example if a user gives as a=1 and b=3 you go through 0,1,2 but your colleague only goes at 1 and 3. I am not sure that this is the problem but you should check out.

edited Dec 04 '20 at 09:53

answered Dec 04 '20 at 09:48

Akis Lionis

23
7

The substraction is just a trick to minimize the number of operations. Look at the problem statement, only additions there – Damien Dec 04 '20 at 10:57
If this is the problem than my code takes some time to execute but it should provide the desired result. But it won't. – Anshul Sharma Dec 04 '20 at 17:59

C++ Array manipulation

1 Answers1