algorithmmathlanguage-agnosticintervals

Can a value reach a given interval by just adding digits?

I've got a given value and interval and want to check if the value, if not inside the interval, can still reach the interval by just adding digits

legende

bottom top value result reason
100 200 150 Inside
10 20 10 Inside
10 20 20 Inside
65 67 5 Never adding 0-9 (=50...59) value will be still < bottom and starting with 500 is already > top
-65 -67 -5 Never adding 0-9 (=-50...-59) value will be still > bottom and starting with -500 is already < top
65 67 50 Never adding 0-9 (=500...509) is already > top
55 57 5 Could adding 0-9 (=50...59), 0-4 will not be in interval, but 5-7 will be
10 60 8 Never adding 0-9 (=80...89) is already > top
100 600 8 Never adding 0-9 (=80...89) is < bottom, but 800 is already > top
100 600 5 Could adding 0-9 (=50...59) is < bottom, but 500 is in interval
100 600 50 Could adding 0-9 (=500...509) is in interval
100 600 5000 Never is already > top
55 400 5 Could adding 0-9 (=50...59) will be in interval starting with 5
550 570 5 Could adding 0-9 (=50...59) is < bottom but starting with 570 value will be in interval

what would be a pure mathematical approach? i thought about using a linear function start at value with a slope of 10 to "simluate" adding digits and then do some sort of intersection test with the interval limits - but im not getting it

can anyone describe a mathematical approach?

i've also developed a small, signed integer, C++ function that gives these answers from the table

bool Reachable( bool signed_input_, int bottom_, int top_, int value_ )
{
    if( 
        ( !signed_input_ && value_ < 0 ) || 
        ( top_ > 0 && value_ > top_ ) ||
        ( bottom_ < 0 && value_ < bottom ) 
    )
    {
        return false;
    }

    while( true )
    {
        top_ = top_ / 10;
        bottom_ = bottom_ / 10;

        if( bottom_ == 0 || top_ == 0 )
        {
            return false;
        }

        if( value_ >= bottom_ && value_ <= top_ )
        {
            return true;
        }
    }
}

but i want to understand if there is also a more mathematical approach possible

Solution

  • A mathematical approach is to use logs, though in practice, one needs to be careful that rounding issues don't create inaccuracies. Here's an approach for positive numbers.

    Suppose x is the number given, B <= T the endpoints of the closed interval in question. Suppose x < B, otherwise it's trivial, then suppose

    (x+1)*10^y >= B+1

    log_10(x+1) + y >= log_10(B+1)

    so, define z as the smallest such integer value

    z = ceil(log_10(B+1) - log_10(x+1)) = ceil(log_10((B+1)/(x+1)))

    then return 'Could' if x*10^z <= T, 'Never' otherwise.