DIGSMPAR Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Srikkanth R
Tester: Harris Leung
Editorialist: Pratiyush Mishra, Jakub Safin

DIFFICULTY:

Cakewalk

PREREQUISITES:

Basic Arithmetic

PROBLEM:

For a positive integer M, let πšπš’πšπš’πšπš‚πšžπš–(𝙼) be the sum of digits of the number M (when written in decimal).

For example, πšπš’πšπš’πšπš‚πšžπš–(𝟷𝟢𝟸𝟹)=1+0+2+3=6.

Given a positive integer N, find the smallest integer X greater than N such that

πšπš’πšπš’πšπš‚πšžπš–(𝙽) and πšπš’πšπš’πšπš‚πšžπš–(πš‡) have different parity, i.e. one of them is odd and the other is even

EXPLANATION:

Let I be the given integer, S be the digit sum, x be the last digit.

Case 1: S+1 has different parity as S
Ans: (I+1)

Case 2: S+1 has same parity as S
\implies x = 9
\implies x+1 = 10
\therefore x for S+1 will be 0 and previous digits would be affected
\implies x+1 = 1
\therefore x for S+2 will be 1 and previous digits won’t be affected
\implies S+2 will have different parity than S+1 and hence, S
Ans: (I+2)

TIME COMPLEXITY:

The above computation can be done in constant time. Hence, the solution has a time complexity of O(1).

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester’s Solution

2

for calculating the sum of digits of n,there would be time complexity of o(log n) , but u said O
(1) , how ??

1 Like
3

It is O(length of n) that is const approx

1 Like
4

okkk ,thnxx i got your point

5 
#include <iostream>
using namespace std;

long int sum(long int n){
    long int temp = n;
    long int sum1 = 0;
    while(temp>0){
        sum1 = sum1 + temp%10;
        temp = temp/10;
    }
    return sum1;
}

int main() {
	int t;
	cin>>t;
	while(t--){
	    long int n;
	    cin>>n;
	    if(n%10 == 9){
	        if(sum(n)%2 == 0){
	            if(sum(n+1)%2==0){
	                cout<<n+2<<endl;
	            }
	            else{
	                cout<<n+1<<endl;
	            }
	        }
	        else{
	            cout<<n+1<<endl;
	        }
	    }
	    else{
	        cout<<n+1<<endl;
	    }
	}
	
	
	return 0;
}

Can someone please tell me , what’s wrong with this solution I am getting correct o/p

6

Hey, there is a problem in the logic of your code.
Here is a test cases on which I found your code’s output wrong wrong

3
9
10
99

Here I have made few changes in your code and it passed, please go through it to understand:

#include <iostream>
using namespace std;

long int sum(long int n){
    long int temp = n;
    long int sum1 = 0;
    while(temp>0){
        sum1 = sum1 + temp%10;
        temp = temp/10;
    }
    return sum1;
}

int main() {
	int t;
	cin>>t;
	while(t--){
	    long int n;
	    cin>>n;
	    if(n%10 == 9){
	        if(sum(n)%2 == 0){
	            if(sum(n+1)%2==0){
	                cout<<n+2<<endl;
	            }
	            else{
	                cout<<n+1<<endl;
	            }
	        }
	        else{
	            if(sum(n+1)%2==1){
	                cout<<n+2<<endl;
	            }
	            else{
	                cout<<n+1<<endl;
	            }
	        }
	    }
	    else{
	        cout<<n+1<<endl;
	    }
	}
	
	
	return 0;
}
7

Why am I getting WA here, please help.

using namespace std;

int main() {
	int t;
	cin >> t;
	
	while(t--){
	    long long n;
	    cin >> n;
	    
	    if(n % 10 == 9){
	        cout << n + 2 << "\n";
	    } else{
	        cout << n + 1 << "\n";
	    }
	    
	    
	}
	return 0;
}
8

It works on test cases. But shows wrong on submit. Can anyone help me find the error?

#include<iostream>
using namespace std;

int main() {
	// your code goes here
    int l;
    cin>>l;
    int n, s;
    while(l--){
        s=0;
       cin>>n;
       int x=n;
       while(s%2==0){
           x=n;
       while(x>0){
           s+=x%10;
           x/=10;
       } 
       n++;
       }
       cout<<--n<<endl;
    }
	return 0;
}
9

Congrats on posting your first query!
Your logic is correct but the implementation is not correct. I have made some changes to your code based on your logic, please go through it.

#include<iostream>
using namespace std;
int digitSum(int n){
    int sum=0;
    while(n>0){
        sum+=n%10;
        n=n/10;
    }
    return sum;
}
int main() {
    // your code goes here
    int l;
    cin>>l;
    int n, s;
    while(l--){
        cin>>n;
        int x=n;
        while(digitSum(n)%2==digitSum(x)%2){// increase the number x until the parity of digitSum of n is not same as parity of digitSum of x
            x++;

        }
        cout<<x<<endl;
    }
    return 0;
}

Please reply if you find any difficulty understanding the code.
Thanks

1 Like
10

Kindly help. Thank you.

11

hey i also used same logic and getting WA, you know why??

12

Hey @mannshah1211 , @kuldeep_singh :wave: ,
your code is giving WA on Test case
1
199
your code is printing 201 (digitsum(199) = 19(odd) and digitsum(201) = 3(odd)).but I should have different parity.