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
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]
I have a better idea : You can say dp[i] = 1 − dp[i − 1]
:)
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.