_Awaken_'s blog

Why vector of enough size giving runtime error(out of bound)
By _Awaken_, history, 21 month(s) ago, In English

Hello,

I have a query which i faced in Round #829 div 2 question 1754B - Kevin and Permutation. When i took vector of required size it is giving me runtime error that is out of bound . but when i took vector of somewhat bigger size it got accepted.

runtime error submission 180120147

accepted submission 180108219

Why the vector of enough required size giving the error??

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

The vector with size n+1 has indices from 0 to n so a[n+1] isn't correct.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    when x ==n+1 the loop will terminate. so "i" never becomes i=n+2, as "i" is increasing by 2. as before termination in loop's last execution ,"i+1" is equal to n.

    So i think it should work but its giving the error.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Suppose n=3, then on 2nd iteration of while i=3 and x=3 and you are trying to access a[4] when your vector has size 4 and indexed 0,1,2,3. This means you're trying to access out-of-bounds element which leads to Undefined Behaviour in C++.

      P. S. This problem does not require using additional memory ;)

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

the value of i+1 is going beyond n+1

i changed the code a bit for debugging

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n ;
        cin>>n;
        vector<int>a(n+1);
     
        int i=1;
        int j=1;
        int x=(n/2)+1;
        while(x!=n+1){

            if(i+1 >= n+1)                                 //added this for debugging
            {
                cout<<"out of bound"<<endl<<i+1<<endl;
            }

            a[i]=x;
            a[i+1]=j;
            x++;
            i+=2;
            j++;
        }

      for(int i=1;i<=n;i++) cout<<a[i]<<" ";
     
      cout<<endl;
     
     
    }
};

for input:

1
243

output:

out of bound
244
RTE

hope this helps

→ Reply