# DIGSMPAR Editorial

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

Cakewalk

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:

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

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

1 Like

okkk ,thnxx i got your point

``````#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

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;
}
``````

``````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;
}
``````

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

``````#include<iostream>
using namespace std;

int main() {
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;
}
``````

Congrats on posting your first query!

``````#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() {
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;
}
``````