codepasta's blog

By codepasta, 3 years ago, In English

hello, codeforce!!!1!

i have a hard question for you, can you please helpp me????

question is: how to find if a number called n is even or odd???? my code is:

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n == 1) cout << "ODD";

if (n == 2) cout << "EVEN";

if (n == 3) cout << "ODD";

if (n == 4) cout << "EVEN";

if (n == 5) cout << "ODD";
if (n == 6) cout << "EVEN";
if (n == 7) cout << "ODD";
if (n == 8) cout << "EVEN";
if (n == 9) cout << "ODD";
if (n == 10) cout << "EVEN";
if (n == 11) cout << "ODD";
if (n == 12) cout << "EVEN";
if (n == 13) cout << "ODD";
if (n == 14) cout << "EVEN";
if (n == 15) cout << "ODD";
}

it works for example, but gives wrong answer for n = 100000, what is wrong???? please helppp

  • Vote: I like it
  • -40
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Here is a dp approach, dp[i] denotes if the ith number is odd or even. Now, the recurrence relaion is dp[i]=dp[i-2]

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    I have a better idea : You can say dp[i] = 1 − dp[i − 1]

    :)

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      another approach would be like this :

      we know that if x is odd then x + 2 is odd as well

      also if x is even x + 2 is even as well

      using that property we can initially start with every number in one component with size one and then merge x and x + 2 using a data structure like DSU.

      in the end we will end up with two components first one will contain all the odd numbers and the other one will contain all the even numbers.