You are given a positive integer N. You have to split each digit of N into either of two non-empty subsequences A or B.
Let us define a function F(X,Y)=(X+Y) \mod 2. Find out whether it is possible to find two non-empty subsequences A and B formed out of N such that F(A,B)=0.
EXPLANATION:
Remember the basic mathematics rule again:
Even + Even = Even \\
Odd + Odd = Even \\
Odd + Even = Odd
As every digit needs to be part of exactly one subsequence A or B. Then observe that the last digit of the given number will be the last digit of any subsequence. Let’s put this digit in the subsequence A.
Last digit of the given number is Even.
It means that the subsequence A is going to be an even number. In order to get the remainder 0 we need to have (X+Y) as even. And for that the subsequence B needs to be also even. Now if there is any digit apart from the last digit in the given number as even we will be able to get the subsequence B also even.
Last digit of the given number is Odd.
It is opposite to that of the above case. Instead of Even we will be looking for odd as the last digit is odd hence the subsequence A will be odd. As odd added to odd only will produce the sum even which will produce the remainder 0.
TIME COMPLEXITY:
O(D), where D is the number of digits in the given number
SOLUTIONS:
Author
for _ in range(int(input())):
n=int(input())
par=(n%10)%2
n=n//10
s='NO'
while(n):
if((n%10)%2 == par ):
s='YES'
n=n//10
print(s)
Tester
#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
t = readInt(1, 1000, '\n');
while(t--){
int n;
n = readInt(10, 1000000000, '\n');
int m = n / 10;
bool f = false;
while(m){
if(m % 2 == n % 2){
f = true;
break;
}
m /= 10;
}
if(f){
cout<<"YES\n";
}else{
cout<<"NO\n";
}
}
return 0;
}
Editorialist
#include<bits/stdc++.h>
using namespace std;
void solve()
{
int n;
cin>>n;
int last_digit = (n%10);
last_digit %= 2;
n = n/10;
while(n)
{
if ((n%10)%2 == last_digit)
{
cout<<"YES"<<endl;
return;
}
n = n/10;
}
cout<<"NO"<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}
whoever has set this question please go and learn about subsequences,
1.there is no hard and fast rule for subsequences to end with the last digit only
2.if you are considering yours way of defining subsequence please mention it properly
(" if N=104N=104, some possible values of (A,B)(A,B) can be (10,4),(14,0)(10,4),(14,0) and (1,4)")
instead of writing “some” you should have written “all”.
#include <bits/stdc++.h>
using namespace std; #define int long long
bool fl;
void solve(string s1, string s2, string &s, int i)
{
if (i == s.size())
{
if (s1.size() > 0 && s2.size() > 0)
{
int n1 = stoi(s1);
int n2 = stoi(s2);
if ((n1 + n2) & 1 ^ 1)
fl = 1;
}
return;
}
if (!fl) {
solve(s1 + s[i], s2, s, i + 1);
solve(s1, s2 + s[i], s, i + 1);
}
}
signed main()
{
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t ;
cin >> t;
while (t–)
{
int n, m, e, o;
fl = 0;
cin >> n;
string s = to_string(n);
solve("", “”, s, 0);
puts(fl ? “YES” : “NO”);
}
}
I don’t understand why you are only seeing the last digit parity and comparing to find that same parity exist in other digits too or not. You had given the example in the question was also including (14 , 0) for 104 where 0 is not the last digit. so we had gone through the idea that if the digit have any two odd numbers or any two even numbers then answer should be YES otherwise NO.
question makers please try to be clear with your ques and also the example given in the question of 104 contradicts your solution explanation.
Can someone check why this doesn’t work?
And why are we considering the last digit to check. If we are able to find two even or two odd digits, we’ll be able to create two subsequences that satisfy the condition.
void solve() {
ll n;
cin >> n;
// we'll be able to create two even or two odd numbers
if(n >= 100) {
cout << "YES" << endl;
return;
}
ll countEven = 0, countOdd = 0;
while(n > 0) {
int digit = n % 10;
if(digit % 2 == 0) {
countEven++;
}
else {
countOdd++;
}
n /= 10;
}
// if we can create two even or two odd numbers
if(countEven == 2 || countOdd == 2) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
I am not getting why we only need to consider the parity of last digit. This contradicts with the example-- 104.
Example- consider numbers 333750,750,570,3750 . According to your code, these numbers can not be considered as answers.
But, according to the example in the question these numbers should be considered as answers such as subsequences of 333750 can be taken as (303,375) .so, it is an answer.
similarly, (7,5) can be taken for 750 and 570 .so, all of these numbers are answer.
But, your code is showing “No”.
so, question makers please give a clear example with questions.
Can you tell me why this solution is not passing all the test cases? Because according to the given example in the problem we can split the number any which way, so if we check that the number has at least two even or/and two odd digits, it must return YES (odd + odd = even, even + even = odd).
#include <bits/stdc++.h> #define ll long long
using namespace std;
int main()
{
int t;
cin >> t;
while (t–)
{
int n;
cin >> n;
int even_cnt = 0;
int odd_cnt = 0;
while(n != 0)
{
int d = n%10;
if(d%2 == 0)
{
even_cnt++;
}
else {
odd_cnt++;
}
n = n/10;
}
if(even_cnt >= 2 || odd_cnt >= 2) cout << "YES" << endl;
else cout << "NO" << endl;
}
you cannot go backwards while splitting numbers,i.e you can only append numbers from the front or skip them.for example 552,you cannot make 25,5 . thats what he meant to say i guess.he should have written all instead of sum
This question needed some more examples so that it would be more clear according to the question we just had to count the number of odds and evens in the number and if either of those is 2 then simply return yes else no. i did this question in log(n/2) time and still it failed some testcases
I used the same logic but it failed. Actually, the no. of odd/even digits can be more than two and still the sum will be even. But also in that case,(>=2 instead of ==2), only one test case passed.
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--) {
long long int n;
int ecount=0, ocount=0;
cin>>n;
while(n!=0) {
int t=n%10;
if(t%2==0) ecount++;
else ocount++;
n/=10;
}
if(ecount>=2 || ocount>=2) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
basically what I did is just counted no of even and odd digit. if No of odd digit and No of even digit are greater than 2 I can make an even no.
But I can’t get an AC for this solution. Can you please help me through? I can’t get on which case my code broke!