Vedkribhu's blog

By Vedkribhu, history, 7 days 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

»
7 days 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.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thanks.

    • »
      »
      »
      7 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Make the dp[100005] global.

      • »
        »
        »
        »
        7 days 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.

        • »
          »
          »
          »
          »
          7 days 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.

        • »
          »
          »
          »
          »
          7 days ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Global arrays are also always initialized.

          • »
            »
            »
            »
            »
            »
            7 days ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

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