Created
July 11, 2019 19:49
-
-
Save adist98/7f67e9e99d77409708e129ddf653b39e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// coder : adist98 | |
// Given two long long integers a and b. The task is to prlong long int | |
// sum of all the digits appearing in the | |
// long long integers between a and b | |
#include "bits/stdc++.h" | |
using namespace std; | |
// Memoization for the state results | |
long long int dp[52][50][50][50][2]; | |
// Stores the digits in x in a vector digit | |
long long getDigits(long long x, vector <long long int> &digit) | |
{ | |
while (x) | |
{ | |
digit.push_back(x%10); | |
x /= 10; | |
} | |
} | |
// Return sum of digits from 1 to long long integer in | |
// digit vector | |
long long digitSum(long long int idx, long long int sum3, long long int sum6, long long int sum9, long long int tight, | |
vector <long long int> &digit) | |
{ | |
// base case | |
if (idx == -1){ | |
if((sum3 == sum6) && (sum6 == sum9) && (sum3 >= 1)){ | |
return 1; | |
}else{ | |
return 0; | |
} | |
} | |
// checking if already calculated this state | |
if (dp[idx][sum3][sum6][sum9][tight] != -1 && tight != 1) | |
return dp[idx][sum3][sum6][sum9][tight]; | |
long long ret = 0; | |
// calculating range value | |
long long int k = (tight)? digit[idx] : 9; | |
for (long long int i = 0; i <= k ; i++) | |
{ | |
// caclulating newTight value for next state | |
long long int newTight = (digit[idx] == i)? tight : 0; | |
if(i == 3){ | |
ret += digitSum(idx-1, sum3+1, sum6, sum9, newTight, digit); | |
}else if(i == 6){ | |
ret += digitSum(idx-1, sum3, sum6+1, sum9, newTight, digit); | |
}else if(i == 9){ | |
ret += digitSum(idx-1, sum3, sum6, sum9+1, newTight, digit); | |
}else{ | |
ret += digitSum(idx-1, sum3, sum6, sum9, newTight, digit); | |
} | |
} | |
if (!tight) | |
dp[idx][sum3][sum6][sum9][tight] = ret; | |
return ret; | |
} | |
// Returns sum of digits in numbers from a to b. | |
long long int rangeDigitSum(long long int a, long long int b) | |
{ | |
// initializing dp with -1 | |
memset(dp, -1, sizeof(dp)); | |
// storing digits of a-1 in digit vector | |
vector<long long int> digitA; | |
getDigits(a-1, digitA); | |
// Finding sum of digits from 1 to "a-1" which is passed | |
// as digitA. | |
long long ans1 = digitSum(digitA.size()-1, 0,0,0, 1, digitA); | |
// Storing digits of b in digit vector | |
vector<long long int> digitB; | |
getDigits(b, digitB); | |
// Finding sum of digits from 1 to "b" which is passed | |
// as digitB. | |
long long ans2 = digitSum(digitB.size()-1, 0,0,0, 1, digitB); | |
return (ans2 - ans1); | |
} | |
// driver function to call above function | |
int main() | |
{ | |
int t; | |
cin >> t; | |
while(t--){ | |
double a,b; | |
cin >> a >> b; | |
cout << rangeDigitSum((long long int)a,(long long int)b) << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment