Algorithm
Problem link- https://www.spoj.com/problems/RAONE/
RAONE - Ra-One Numbers
In the War between good and evil . Ra-One is on the evil side and G-One on the good side.
Ra-One is fond of destroying cities and its G-one's duty to protect them..
Ra-One loves to destroy cities whose Zip Code has special properties. He says he loves to destroy cities which have Ra-One numbers as their Zip Code.
Any number is Ra-one if the Difference between Sum of digits at even location and Sum of digits at odd location is One (1).. For eg... for 234563 is Ra-One number
digits at odd location are 3,5,3 (unit place is location 1 )
digits at even location are 2,4,6
Diff = (2+4+6)-(3+5+3)=12-11 = 1.
And 123456 is not Ra-One number
diff = (5+3+1) - (2+4+6) = -4
G-One knows this about Ra-one and wants to deploy his Army members in those cities. 1 army member will be deployed in each city.
G-one knows the range of ZIP-Codes where Ra-One might attack & needs your help to find out how many army members he needs.
Can you help Him ?
Input
First line will have only one integer 't' number of Zip-Code ranges. it is followed by t lines
Each line from 2nd line contains 2 integer 'from' and 'to'. These indicate the range of Zip codes where Ra-one might attack. ('From' and 'to' are included in the range)
NOTE:'t' will be less than 100. 'from' and 'to' will be between 0 and 10^8 inclusive.
Output
A single number for each test case telling how many army members G-One needs to deploy.
each number should be on separate lines
Example
Input: 2 1 10 10 100 Output: 1 9
explanation:
for 1st test case the only number is 10
for 2nd test case numbers are 10, 21, 32, 43, 54, 65, 76, 87, 98
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e5+5;
string a, b;
ll dp[10][105][105][2];
int n;
ll solve(string &s, int idx, ll sumEven, ll sumOdd, int constructedPrefixIsEqualtoPrefix){
if(dp[idx][sumEven][sumOdd][constructedPrefixIsEqualtoPrefix] != -1)
return dp[idx][sumEven][sumOdd][constructedPrefixIsEqualtoPrefix];
ll res = 0;
if(idx == n){
res = (sumEven-sumOdd == 1) ? 1 : 0;
}else{
if(constructedPrefixIsEqualtoPrefix){
for(int i = 0; i <= s[idx]-'0'; i++){
if(i == s[idx]-'0'){
// if(idx&1)
// res += solve(s, idx+1, sumEven, sumOdd + i, 1);
// else
res += solve(s, idx+1, sumOdd, sumEven + i, 1);
}
else{
// if(idx&1)
// res += solve(s, idx+1, sumEven, sumOdd + i, 0);
// else
res += solve(s, idx+1, sumOdd, sumEven + i, 0);
}
}
}else{
for(int i = 0;i < 10; i++){
// if(idx&1)
// res += solve(s, idx+1, sumEven, sumOdd + i, 0);
// else
res += solve(s, idx+1, sumOdd, sumEven + i, 0);
}
}
}
dp[idx][sumEven][sumOdd][constructedPrefixIsEqualtoPrefix] = res;
return res;
}
ll f(string& a){
ll sumOdd = 0;
ll sumEven = 0;
bool odd = true;
for(int i = (int)a.size()-1; i >= 0; i--){
if(odd){
sumOdd += a[i] - '0';
odd = false;
}
else{
sumEven += a[i] - '0';
odd = true;
}
}
return (sumEven-sumOdd == 1);
}
int main(){
io;
int t;
cin >> t;
while(t--){
cin >> a >> b;
memset(dp, -1, sizeof dp);
n = b.size();
ll ansR = solve(b, 0, 0, 0, 1);
memset(dp, -1, sizeof dp);
n = a.size();
ll ansL = solve(a, 0, 0, 0, 1);
ll ans = ansR - ansL + f(a);
cout << ans << endl;
}
return 0;
}Input
1 10
10 100
Output
9
Demonstration
SPOJ Solution-Ra-One Numbers-Solution in C, C++, Java, Python