Vedkribhu's blog

Why this c++ code fails for larger input?
By Vedkribhu, history, 4 years ago, In English

Problem: link Code in c++ which produces different output for k=10^5. Same logic in python giving AC.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long p = 1e9+7;
 
int main(){
	ll k;cin>>k;
	ll i,j,dp[100005], par[2] = {1,0};
	for(i=1;i<k+1;i++){
		dp[i]+=(par[(i+1)%2])%p;
		par[i%2]+=(dp[i])%p;
	}
	cout<<dp[k]%p<<endl;
}
  • Vote: I like it
  • -22
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

The array dp[] is not initialized, ie contains random values at begin.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanks.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Make the dp[100005] global.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Don't, use vector instead, they are always initialized and the performance penalty is not more than homeopathic.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the advice. I am new to c++, learning new things everyday.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Global arrays are also always initialized.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            Except if they are not global. Vectors are really allways initialized.

            → Reply