Count all numbers up to A that have sum of digits equal to S

1 <= A < 10^15
1 <= S <= 135
আমরা যদি A পর্যন্ত সকল সংখ্যা generate করি এবং sum এর সমান কিনা তা check করি তাহলেই আমরা আমাদের answer পেয়ে যাব।

000

001

.

.

188

189

.

.

244

245

.

.

257

258

আমাদের কে প্রথমে জানতে হবে ডিজিট সংখ্যা কয়টি। এখানে আমরা ৩ ডিজিট এর সংখ্যা ধরেছি A।

আমরা ৩ ডিজিট এর সকল সংখ্যা generate করতে পারব। কিন্তু A এর উপরের সংখ্যা generate করে আমাদের কোন লাভ হবে না। তাই A পর্যন্ত limit দিয়ে  ৩ ডিজিট এর সংখ্যা generate করব।

আমরা আগেই n ডিজিট এর সকল সংখ্যা কিভাবে generate করা যায় তা দেখেছি এখানে।

এখন আমরা দেখবো A পর্যন্ত limit কিভাবে সেট করা যায়।

আমরা একটা recursive function লেখতে পারি। যার প্যারামিটার হবে 3ta  current_digit_no  ,sum_left , limit ।

আমরা এভাবে চিন্তা করতে পারি A = 2(0 তম ডিজিট ) 5 (1 তম ডিজিট) 6 (2 তম ডিজিট) 8 (3  তম ডিজিট)।

function er limit parameter আমাদের বলবে আমরা যে ডিজিট এ আসছি তার limit পর্যন্ত নিতে পারব না সব সংখ্যা নিতে পারব।

০ তম ডিজিট এর জন্য আমরা highest ২ পর্যন্ত generate করতে পারব, আমরা যদি ০ তম ডিজিট এ ২ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ৫ পর্যন্ত genetare করতে পারব, আবার আমরা যদি ০ তম ডিজিট এ ০/১ নিয়ে আগাই তাহলে ১ তম ডিজিট এ ০-৯ পর্যন্ত  সব গুল ডিজিট নিয়ে আগাইতে পারব। পরের ডিজিট এর জন্য same কাজ হবে।

আমরা limit এর ২টা value ঠিক করব।

যখন limit == 0 তখন প্রতিবার ০ - ৯ এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব আর limit 0 পাথাব।

আর যখন limit == 1 তখন ঐ ডিজিট এর highest_limit বের করব। প্রতিবার ০ ঠেকে  highest_limit এর মধে সবগুলো সংখ্যা নিয়ে একবার আগাবো যদি sum_left - সংখ্যা >= ০ হয় সাথে sum_left থেকে সংখ্যা টা বিয়োগ করে দিব। সংখ্যাটা highest_limit এর চে ছোট হলে limit = 0 পাঠাব আর highest_limit এর সমান হলে limit = 1 পাঠাব।

BaseCase:

যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ হয়ে যায় তার মানে আমরা এমন একটা n ডিজিট বিশিষ্ট সংখ্যা পায়ে গেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান। তাই আমরা ১ return করব।

যদি current_digit_no যদি n হয়ে যায় আর sum_left ০ না হয় তার মানে আমরা যে সংখ্যা generate করেছি যার ডিজিট গুলোর যোগ ফল sum এর সমান না। তাই আমরা ০ return করব।

dynamic programming:

function টার recursive tree আঁকলে দেখবো যে এখানে overlapping subproblem পাওয়া যাবে। তাই যদি আমরা memorization করতে পারি। 

UseFull Links:

• Count of numbers between A and B (inclusive) that have sum of digits equal to S StackOverFlow
• Counting problems from A to B (CodeForces)

Problem: 

• Sum of Digits

	#include<bits/stdc++.h>
	using namespace std;
	string s;
	int n;
	int dp[10][95][3]; // digit number max = 10 (0<=A<=10^10)
	/// as there can be at most 10 digit the max sum can be 9*10 = 90 so if input sum > 90 then answer will be 0
	string int_to_string(int a){
	stringstream ss;
	ss << a;
	string str = ss.str();
	return str;
	}
	long long f(int current_digit_no,int sum_left,int limit){
	if(current_digit_no==n){
	if(sum_left==0) return 1;
	return 0;
	}
	if(dp[current_digit_no][sum_left][limit]!=-1) return dp[current_digit_no][sum_left][limit];
	long long total = 0;
	if(limit==0){
	for(int i=0;i<10;i++){
	if((sum_left-i)>=0) total += f(current_digit_no+1,sum_left-i,0);
	}
	}
	else{
	int highest_limit = (int) (s[current_digit_no] - '0');
	for(int i=0;i<=highest_limit;i++){
	if((sum_left-i)>=0){
	if(i==highest_limit) total += f(current_digit_no+1,sum_left-i,1);
	else total += f(current_digit_no+1,sum_left-i,0);
	}
	}
	}
	return dp[current_digit_no][sum_left][limit] = total;
	}
	int main(){
	int a,sum;
	cin>>a>>sum;
	s = int_to_string(a);
	n = s.size();
	memset(dp,-1,sizeof(dp));
	long long z = f(0,sum,1);
	cout<<z<<"\n";
	}

view raw count of numbers upto A that have sum of digits equal to S.cpp hosted with ❤ by GitHub