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
, and two large numbers in the form of string
and
.
Count the number of values between
to
(both inclusive) that are divisible by
, 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
The second line contains
The third line contains
Output
Output the answer modulo
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).
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;
}