Skip to content

Instantly share code, notes, and snippets.

@adist98 adist98/369.cpp
Created Jul 11, 2019

Embed
What would you like to do?
// 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
You can’t perform that action at this time.