0

i have two arrays, i wanted to output only the later one, but in the output an element just got a garbage value. but, if i printed the first array before it then the garbage value in the second array isn't outputted anymore (well, i had to compile & run 3/4 times in order to get the correct value once, the remaining 2/3 times i get the garbage value)

( i run my code without printing the first array in codechef.com/ide , and it gave the desired output every time. )

so i have two questions.

  1. why did this happen?

  2. why did this happen only to my & not to the oj?

i was trying to implement heap build, that is to take an array a , put this array to another array called heap in a way that the heap follows the property of Binary Min Heap . lastly, print the elements of heap . when i compiled and run it, it outputted a garbage value instead of a certain element's value each time. then , to debug it , i took a loop before printing the heap in order to print the a array to see if it takes the inputs correctly. this time, the heap array was printed correctly! but when i again compile and run it, it gave me the same garbage value instead of an element's value as before. i just began to compile and run the code for some times. i noticed that, in every 3/4 compilations , it gave correct answer just once.

later i submitted my code in codechef's ide, this time i got the correct output every time without having printing the extra array a. 

#include <bits/stdc++.h>

using namespace std;

int main(void)
{ 
    int a[10];

    for (int i = 0; i < 6; i++)
    {
        cin >> a[i];
    }

    int heap[10];

    for (int i = 0, h = 1; i < 6; i++, h++)
    {
        if(h == 1) heap[h] = a[i];
        else{
            heap[h] = a[i];
            int k = h;
            //checking if the new heap element violates the heap property
            //if it does then swap with it's parent , and repeat
            while(k){
                if(heap[k] < heap[k/2]) swap(heap[k], heap[k/2]);
                k /= 2;
            }
        }
    }
    /* if this part is executed then the heap printing
    // part prints the correct heap array atleast one time
    // in every 3 or more than 3 "build & run" without any garbage value

    //if not executed, then the heap printing part prints a 
    //garbage value each and every time 
    */

    // weird start
    //prints the main array
    // for (int i = 0; i <= 5; ++i)
    // {
    //  cout << a[i] <<' ';
    // }
    // cout << endl;
    //weird end

    //heap printing part
    for (int i = 1; i <= 6; ++i)
    {
        cout << heap[i] << ' ';
    }
    cout << endl;
    return 0;
}

for input: 6 5 1 4 2 3

i expected: 1 2 3 6 4 5

i got: 2 4 3 6 5 4199040

(editor: sublime text and codeblocks & compiler: minGW)

update: replacing while(k) with while(k/2) did the job for outputting the answer without any help printing of another array. but how did the code generated a two different output in several build & run operations in my device? and it every time outputted the right answer in the online ide but not in mine. (this was the main question actually)

Ardhendu
  • 1
  • 2
  • 1
    Please **[edit]** your question with an [mcve] or [SSCCE (Short, Self Contained, Correct Example)](http://sscce.org) – NathanOliver May 22 '19 at 17:53
  • 4
    You seem to have an off-by-one error in iterating over your array. You're ranging from 1 to 6, inclusive, which seems like it ought to be 0 to 5, inclusive. – templatetypedef May 22 '19 at 17:53
  • @NathanOliver i am new to stack overflow in terms of asking questions. i didn't get exactly what you said, but i tried to edit it. is it okay now? – Ardhendu May 22 '19 at 17:59
  • `swap(heap[k], heap[k/2]` - for k == 1, k/2 == 0. – 500 - Internal Server Error May 22 '19 at 18:09
  • @templatetypedef , the heap is 1 indexed, and the a is 0 indexed.i checked it, it was not the problem. :/ and if it was the case, then online ide should've produced the same output(with garbage), right? :/ – Ardhendu May 22 '19 at 18:10
  • @500-InternalServerError , k won't take the value 1. cause if h == 1, it just assigned heap[h] with a[i], and didn't do any swapping or assigning values to k. – Ardhendu May 22 '19 at 18:14
  • In your while statement you can have `k/2`equal to 0. – Qubit May 22 '19 at 18:16
  • @Ardhendu: you have it in a `while` loop, winding it down. – 500 - Internal Server Error May 22 '19 at 18:17
  • Show a great deal of caution with `#include `. You should not directly call anything in the bits directory. They are implementation-specific headers and aren't guaranteed to work if included directly. For specifics on bits/stdc++.h's downsides read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). When you combine it with `using namespace std;`, you turn the global namespace into a minefield. Tens of thousands of identifiers can now conflict with your declarations causing bizarre errors. – user4581301 May 22 '19 at 18:24
  • @500-InternalServerError thank you, i have changed it to ` while(k/2)` , but why did it happen to only my device and not the online ide with the same input? – Ardhendu May 22 '19 at 18:25
  • @Ardhendu Overwriting an array leads to undefined behavior. There is no guarantee what your output will be if you go beyond the bounds of the array. So all of those things you were doing (every 3 or 4 times it works, but fails, etc.) just had you waste your time. If you see it wrong just once, just stop everything and fix the problem. Also, if you had used `std::array` instead of the usual arrays, and used `at()` instead of `[ ]` to access the elements, then all of the environments you tested on would have failed with an `out_of_range` exception. – PaulMcKenzie May 22 '19 at 18:27
  • @Ardhendu Also, a comment about the code you posted -- instead of having the input being done using `cin` statements, please populate the array in the code directly. For example `int a[10] = {6,5,1,4,2,3};`. No one is going to type in the data over and over again each time they run the program. – PaulMcKenzie May 22 '19 at 18:33
  • @PaulMcKenzie it was helpful, thank you ! – Ardhendu May 22 '19 at 18:45
  • @Ardhendu [Here is the program, with the arrays having size 6 using std::array](http://coliru.stacked-crooked.com/a/0ab18f0be5087a41). Note the exception -- every standard compiler will run and give you the same exception (std::out_of_range). Look at where the `at()` calls are placed -- that is where you're going out-of-bounds. Your original code covered up this bug by making the arrays too big. Making the arrays the correct size revealed the error. That's the danger of making arrays too big -- it covers up off-by-one bugs like this. – PaulMcKenzie May 22 '19 at 18:47
  • @PaulMcKenzie The point here is that he isn't using the first element (for some undisclosed reason), so using `std::array` rather than a static array would in fact not resolve this particular issue. On top of that, bounds checks aren't free (although not very expensive either), and while certainly helpful at times, I don't think it makes sense to blindly use them everywhere just because you can. – Qubit May 23 '19 at 01:36
  • @Qubit I am well-aware of what `at()` does. The reason why I used it is for debugging purposes. Once the off-by-one bugs are cleaned up, then `[ ]` is reintroduced. You won't believe the thousands of posts that would never need to be here if the original poster's knew about this technique of *debugging*. – PaulMcKenzie May 23 '19 at 01:38
  • thank you everyone. i got my answer. so the main reason was: in the loop i set the condition to be `while(k)` but inside there was a `k/2` , so it turned out that for `k = 1`, my program had accessed `heap[k/2]` that is `heap[0]`, but i started putting values in heap from index 1. so the garbage value in `heap[0]` was swapped in the main heap array if it was larger than `heap[k]`. as for codechef ide, *heap[0]'s* value was small enough for not to be swapped. but in my environment, the value was (most of the time) large enough to be swapped. that's where the problem began. again thanks everyone – Ardhendu May 23 '19 at 12:01

0 Answers0