CODEWITHSUNDEEP
algorithmdynamic
know dont
know dont

Reputation: 179

How many unlucky numbers in segment [a;b]?

Some numbers are called unlucky if their decimal representation contain the number 5.

For example: 123456, 245, 1555 are unlucky numbers and 111, 123, 147 are not unlucky numbers.

How many unlucky numbers are there in segment [a:b]?, where 1 < a < b.

For example a = 1, b = 17 , we have the result is 2. Because, there are only 5, 15.

This is my try: I call f(a) is the amount of unlucky numbers in segment [1;a], then we have f(a+1) is the the amount of unlucky numbers in segment [1;a+1], so we have: f(a+1)=f(a) if a+1 is not unlucky number and f(a+1)=f(a)+1 if a+1 is unlucky number. My problem is to compute f(a) with O(log(n)), but I can't come to good solution!

Upvotes: 3

Views: 111

Answers (2)

Photon
Photon

Reputation: 2777

This can be easilly solved in O(log N) time using dynamic programming known as "dp on digits"

First note that instead of calculating unlucky numbers in inertval [L,R] we can instead define some function f(X) that calculates unlucky numbers in interval [0,x], so unlucky numbers in interval [L,R] can be calculated as f(R) - f(L-1)

Creating function f() is kinda straightforward, we have our state as dp[pos][ls][unlucky] where:

  • pos - current digit we are trying to fill
  • ls - just a flag that saysif our prefix matches the limit of how high we can go
  • unlucky - another flag that says if our number is already unlucky or not

Then we can do simple recursion expansion digit by digits + memoization.

Sample code (C++11) :

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll dp[51][2][2];
ll digits[51];
int amount_of_digits;

ll solve(ll pos, ll ls, ll unlucky)
{
    if(pos >= amount_of_digits)return unlucky;
    if(dp[pos][ls][unlucky]!=-1)return dp[pos][ls][unlucky];

    dp[pos][ls][unlucky]=0;

    for(int i=0; i<=(ls ? 9 : digits[pos]); i++) //next digit
        dp[pos][ls][unlucky]+=solve(pos+1,ls | (i<digits[pos]), unlucky | (i==5));

    return dp[pos][ls][unlucky];
}

ll f(ll x)
{
    string s = to_string(x);
    amount_of_digits = s.size();

    for(int i=0; i<s.size(); i++)
        digits[i] = s[i]-'0';

    memset(dp, -1, sizeof dp);
    return solve(0,0,0);
}

ll calc_interval(ll L, ll R)
{
    return f(R) - f(L-1);
}

int main()
{
    cout<<calc_interval(2,17);
}

Upvotes: 2

Bernard
Bernard

Reputation: 5676

I won't give you the full solution, but I'll give you a hint that should point you in the correct direction. You need to apply some mathematics (permutation & combination) knowledge to this problem.

Suppose you want to find the number of unlucky numbers in [0, 12345). With some math, you can calculate the number of such numbers in [0, 10000) in O(1). Then, you could calculate the number of such numbers in [10000, 12000) in O(1). Then do it for [12000, 12300). Now if you see where we're going...

To find the number of unlucky numbers in [a, b], we can simply calculate the number of unlucky numbers in [0, a) and the number of unlucky numbers in [0, b+1).

Note: You don't actually need to calculate the number of unlucky numbers in [0, 10000) in O(1). It also suffices to find a way to calculate the number of unlucky numbers in [0, 10000) from the number of unlucky numbers in [10000, 12000) in O(1).

Upvotes: 3

Related Questions