1

I have long been declaring a lot more space for arrays during competitive programming.

int pr[100010]; //for example

However, when I was trying to declare an array for a smaller space this morning, things went wrong.

#include <iostream>
using namespace std;

int main()
{
    int n; cin >> n;

    int pr[100]; //seems enough
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;

        pr[i] = pr[i-1] + x;
    }

    for(int i = 1; i <= n; i++)
        cout << pr[i] << endl;
    return 0;
}

You see, this program was for calculating the prefix sum of an array. The value for this array comes from input. The space for this array seems enough. But when I input these to my program and found that it occurs to a wrong output:

//the input:
5
1 2 3 4 5

//the output:
1875947561
1875947563
1875947566
1875947570
1875947575

The array might just out of bounds. I thought. However, when I modified the space 100 to 10, the answer was correct this time!

#include <iostream>
using namespace std;

int main()
{
    int n; cin >> n;

    int pr[10]; //smaller, but correct!
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;

        pr[i] = pr[i-1] + x;

        cout << "*" << pr[i] << endl;
    }

    for(int i = 1; i <= n; i++)
        cout << pr[i] << endl;
    return 0;
}

5
1 2 3 4 5

1
3
6
10
15

It seems that the problem happend at here:

pr[i] = pr[i-1] + x;

I know that the initial value of the array was 0, but why a smaller space works well and the higher space didn't ? The most interesting thing is that when I declare the array as a global variable, though small, the answer was correct?

#include <iostream>
using namespace std;

int pr[1]; //such a tiny space but correct!

int main()
{
    int n; cin >> n;

    for(int i = 1; i <= n; i++) {
        int x; cin >> x;

        pr[i] = pr[i-1] + x;
    }

    for(int i = 1; i <= n; i++)
        cout << pr[i] << endl;
    return 0;
}

The results:

//the input
5
1 2 3 4 5

//the output
1
3
6
10
15

This problem confuses me a whole day, can someone help me? I can't fell asleep as the problem was still there :(

Modermjaymi
  • 33
  • 4
  • [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – Jesper Juhl Oct 23 '22 at 07:54
  • 2
    "_I know that the initial value of the array was 0_": No, it was not. – user17732522 Oct 23 '22 at 07:55
  • https://en.cppreference.com/w/cpp/language/ub – Jesper Juhl Oct 23 '22 at 07:55
  • https://www.learncpp.com/cpp-tutorial/uninitialized-variables-and-undefined-behavior/ – user17732522 Oct 23 '22 at 07:57
  • 2
    Why are you still using C style arrays? For any array that uses user input for its size, use std::vector. Note : if your teacher told you to do this then ask him to tell your class about std::vector too. https://www.learncpp.com/cpp-tutorial/an-introduction-to-stdvector/ – Pepijn Kramer Oct 23 '22 at 07:58
  • Declaring an automatic storage-duration array of size `100010` will also be bad idea btw. It is likely to cause you a stack overflow. Use `std::vector` and you won't have any of the initialization or memory issues. – user17732522 Oct 23 '22 at 07:58
  • My teacher also didn't initialize the array, instead, he declares a large, global array – Modermjaymi Oct 23 '22 at 08:02
  • 1
    Global variables in C++ are also not a good idea... https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#i2-avoid-non-const-global-variables. Well intended advice : All in all I think your teacher should update his material (based on all of those C++ guidelines). Also note : don't look at the code on competitive coding sites you will only pickup bad habits. – Pepijn Kramer Oct 23 '22 at 08:03
  • 1
    **I know that the initial value of the array was 0**, no you don't, local variables if not initialised contain undefined values... – Jean-Baptiste Yunès Oct 23 '22 at 08:10

2 Answers2

2

The problem is here:

int pr[100]; //seems enough
for(int i = 1; i <= n; i++) {
    int x; cin >> x;

    pr[i] = pr[i-1] + x; // uninitialized read of pr[0]
}

Reading an uninitialized variable is undefined behavior. In this case you read some garbage value, but your program could also crash or produce other unexpected results.

As a side note, your program does not need an array at all. You could output each value as soon as you calculate it, and store the current sum in a scalar.

John Zwinck
  • 239,568
  • 38
  • 324
  • 436
  • Yes! But may I ask why declaring a global variable can solve this? – Modermjaymi Oct 23 '22 at 08:00
  • ".... or produce other unexpected results", like giving the misleading impression of working correctly for smaller arrays. – Yunnosch Oct 23 '22 at 08:00
  • 1
    Modermjaymi, what did your learning via "competitive programming" teach you about the differences of local and global variables? Sorry for that jibe against that kind of sites, but a programming class or a book usually have some content on what differences there are. And this one is unlikely to become obvious in a programming style which assumes sizes of C-style arrays in C++. (I assume that John Zwinck will eleborate in this answer. otherwise let me know in a few days. Then I will.) – Yunnosch Oct 23 '22 at 08:01
  • @Modermjaymi global variables like that are implicitly initialized to zero, but using `int pr[1]` is clearly not valid either. If you run the `int pr[1]` version with a tool like Address Sanitizer you will see errors. – John Zwinck Oct 23 '22 at 08:05
  • :-) I knew you would. – Yunnosch Oct 23 '22 at 08:05
  • I know that global variables are used in the whole program, and local variables can only be used in functions – Modermjaymi Oct 23 '22 at 08:12
  • 1
    Wow! This is the first time I know this. Looks like there's still a lot to learn :) – Modermjaymi Oct 23 '22 at 08:16
1

Conclusion

If you declare a global variable, it would be initialized to zero. For a local variable, you have to initialize it before use. For that global pr[1], it can work, but with error.

Modermjaymi
  • 33
  • 4