# Count Odd Even Numbers DSA Problem Solution

Count Odd Even Numbers DSA Problem Solution

In this post, we are going to solve Count Odd Even Numbers DSA Problem from Walmart, Online Assessments and On-Campus Interview. Let’s have a look at the problem statement first and then try to solve the problem.

## Count Odd Even Numbers DSA Problem Statement

Given an integer

$p$$p$, and two large numbers in the form of string

$L$$L$ and

$R$$R$.

Count the number of values between

$L$$L$ to

$R$$R$ (both inclusive) that are divisible by

$p$$p$, and the number should have even value at the odd indices and odd values in the even indices.

Input

The first line contains an integer

$p\left(1\le p\le 25\right)$$p(1 \le p \le 25)$

The second line contains

$L\left(1\le L\le {10}^{99}\right)$$L(1 \le L \le 10^{99})$

The third line contains

$R\left(L\le R\le {10}^{99}\right)$$R(L \le R \le 10^{99})$

Output

${10}^{9}+7$$10^{9}+7$

Examples
Input
7
1
25

Output
2
Input
2
8
15

Output
0
Note

In the given sample case, there are 3 numbers divisible by 7 in the range of 1 to 25.

• 7 – at index 0(even), we have value 7(odd).
• 14 – at index 0(even), we have value 4(even), so do not count
• 21 – at index 0(even), we have value 1(odd) and at index 1(odd), we have value 2(even).

## Problem Solution in C++

#include<bits/stdc++.h>
using namespace std;

int dp[105][2][2][2][30];

const int M = 1e9 + 7;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int p;
cin >> p;
string s, t;
cin >> s >> t;
int n = s.size();
int m = t.size();
s.insert(s.begin(), m - n, '0');
memset(dp, -1, sizeof(dp));

function<int (int , int, int , int, int)> countNumbers = [&] (int i, int low, int high, int pos, int val) -> int{
if(i == m)    return pos > 0 && val == 0;
if(dp[i][low][high][pos][val] != -1)    return dp[i][low][high][pos][val];
int ans = 0;
int _low = (low == 1 ? s[i] - '0' : 0);
int _high = (high == 1 ? t[i] - '0' : 9);
for(int j = _low; j <= _high; j += 1){
if(j == 0 && pos == 0){
ans = (ans + countNumbers(i + 1, (low == 1 && j == _low), (high == 1 && j == _high), pos, val)) % M;
}
else if(((m - i - 1) & 1) != (j & 1)){
ans = (ans + countNumbers(i + 1, (low == 1 && j == _low), (high == 1 && j == _high), 1, (val * 10 + j) % p)) % M;
}
}
return dp[i][low][high][pos][val] = ans;
};
cout << countNumbers(0, 1, 1, 0, 0);
return 0;
}