Count substrings Wrong Answer

general
,
1

I have been doing the count substrings problem which is from the July contest. My code is getting the wrong answer and I have no idea what is going wrong. Below is my code:

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int main(int argc, char const *argv[])
{
    int T, N;
    string str;
    scanf("%d", &T);

    while (T--) {
        scanf("%d", &N);
        int counter = 0;
        cin >> str;
        for (int i = 0; i < N; i++) {
            if (str[i] - '0' == 1) counter++;
        }

        printf("%d\n", (counter * (counter + 1)) / 2);
    }
    
    return 0;
}
2

Use long long int to store the value of counter.

When you use int to store counter, the result of count*(count+1) is int, it exceeds the limit of int and and leads to overflow and hence the Wrong answer(WA).

This should get you AC. If you still have any problem, you can comment below.

1 Like
3

Why would it make a difference to use long long int instead of just int.

4

Hi, @darkking

Corrected solution http://www.codechef.com/viewsolution/4337491

Happy coding…:slight_smile:

1 Like
5

maximum value of count can be 100000 agreed as n<=100000.

count*(count+1) becomes of the range of 10^10

now as count is int the result will also be int
this value can not fit into int. As int is only 4 bytes and so is long int.

And also take a look at the link provided by @tech_boy below, it will be helpful.

6

Read range of data types in C++

http://www.cplusplus.com/forum/beginner/44774/

1 Like