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$, and two large numbers in the form of string

$L$ and

$R$.

Count the number of values between

$L$ to

$R$ (both inclusive) that are divisible by

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

The first line contains an integer

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

The second line contains

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

The third line contains

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

Output the answer modulo

${10}^{9}+7$

7 1 25

2

2 8 15

0

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).

So, the answer is 2.

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

## Leave a Reply