So I have written the logic of picking both the shoes (left and right) once at a time and check if the sum that they add upto is odd or not.If the sum is odd then I return 1(correct method) else I return 0(wrong method)
There goes the code for the same
#include<bits/stdc++.h>
#define ll long long
#define endl ā\nā
#define fast ios::sync_with_stdio(false); cin.tie(nullptr); cin.tie(nullptr);
using namespace std;
ll baliGame(vector<pair<ll, ll>> &shoes, vector &dp, ll i = 0, ll sum = 0) {
if (i == shoes.size()) {
if (sum & 1)
return 1;
else
return 0;
}
if (dp[i] != -1)
return dp[i];
ll leftShoe = baliGame(shoes, dp, i + 1, sum + shoes[i].first);
ll rightShoe = baliGame(shoes, dp, i + 1, sum + shoes[i].second);
dp[i] = (((leftShoe%(1000000000+7)) + (rightShoe%(1000000000+7))))%(1000000000+7);
return dp[i];
}
int main() {
fast
ll n;
cin >> n;
vector<ll> dp(n + 1, -1);
vector<pair<ll, ll>> shoes;
while (n--) {
ll first, second;
cin >> first >> second;
shoes.push_back({first, second});
}
cout << baliGame(shoes, dp) << endl;
}