Find the Occurence of Digit x in range [L,R] includeing

hackerscode's blog

By hackerscode, history, 6 years ago, In English

This approach is in O(n) i tried to find better approcah // https://www.geeksforgeeks.org/find-the-occurrences-of-y-in-the-range-of-x/

but I cannt find any approch please suggest me..

hackerscode
6 years ago
3

Comments (3)

Write comment?

titanoBEBRA

6 years ago, hide # |

← Rev. 6 →

Let $$$f_{x,y}$$$ be the quantity of digits $$$y$$$ among numbers $$$[0, x]$$$.
Then to answer the query $$$l, r, d$$$ is simply $$$f_{r,d} - f_{l-1,d}$$$.
Preprocissing is $$$O(n * log_{10}n)$$$, and each query if $$$O(1)$$$.
So the total complexity is $$$O(n * log_{10}n + q)$$$.

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x)              (x).begin(), (x).end()
#define inf                 1e18

using namespace std;

void solve() {
	int n, q;
	cin >> n >> q;

	vector < vector <int> > dp(n + 1, vector <int> (10)); dp[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		dp[i] = dp[i - 1];

		ll a = i;
		while (a) {
			++dp[i][(a % 10)];
			a /= 10;
		}
	}
	while (q--) {
		int l, r, d;
		cin >> l >> r >> d;
		cout << dp[r][d] - ((!l) ? 0 : dp[l - 1][d]) << '\n';
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	ifstream cin("input.txt");
//	ofstream cout("output.txt");
	int q = 1; // cin >> q;
	while (q--) solve();
}

→ Reply

titanoBEBRA

6 years ago, hide # ^ |

← Rev. 4 →

By the way, I think there's a more efficient way to solve this problem:
at first read https://codeforces.me/blog/entry/77096 if you aren't familiar with digit dp.
After this we have a $$$dp_{i,j,flag} - $$$ quantity of numbers of length $$$i$$$ with $$$j$$$ digits $$$x$$$, and flag tells us whether our prefix of length $$$i$$$ is equal to prefix of length $$$i$$$ of number $$$n$$$ (you can read about it more in the blog I mentioned above).

C++ code

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x)              (x).begin(), (x).end()
#define inf                 1e18

using namespace std;

void solve() {
	ll n, x;
	cin >> n >> x;
	vector <int> dig;
	if (!n) dig.resize(1, 0);
	else {
		while (n) {
			dig.push_back(n % 10);
			n /= 10;
		}
		reverse(all(dig));
	}
	n = dig.size();
	ll dp[n + 1][50][2];
	memset(dp, 0LL, sizeof(dp));

	dp[0][0][1] = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 50; ++j) {
			for (int flag : {0, 1}) {
				for (int d = 0; d < 10; ++d) {
					if (flag && d > dig[i]) continue;
					if (j + (d == x) >= 50) continue;
					int new_j = j + (d == x);
					int new_fl = flag & (d == dig[i]);
					dp[i + 1][new_j][new_fl] += dp[i][j][flag];
				}
			}
		}
	}
	ll cnt = 0;
	for (int j = 1; j < 50; ++j) {
		cnt += (dp[n][j][0] + dp[n][j][1]) * j;
	}
	cout << cnt;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//	ifstream cin("input.txt");
//	ofstream cout("output.txt");
	int q = 1; // cin >> q;
	while (q--) solve();
}

Time complexity is $$$O(log_{10}n)$$$

→ Reply

SPyofgame

6 years ago, hide # |

You can try dp-digit

Lets $$$f(n)$$$ be the function that find the occuence of digit $$$x$$$ in range $$$[0, n]$$$, then the result will be $$$f(r) - f(l - 1)$$$

Notice that both number should have same digits length

My approach using recursive

Pseudo code

// call with magic(head, false, 0)
vector<digit> n; /// something like: {2,7,0,2,2,0,0,4} - 27022004
ll magic(int pos, bool isLess, int cnt)
    if (pos < 0) return cnt;
    
    ll &res = f[pos][isLess][cnt];
    if (res is calculated) return res;

    int lim = (isLess) ? 9 : n[i];
    for (each next_digit in range [0, lim])
        if (next_digit = x) next_cnt = cnt + 1
        if (next_digit < lim) next_isLess = true
        res = res + magic(digit + 1, next_isLess, next_cnt)

    return res

The complexity

→ Reply