Check for a number with numbers in C ++

Question

I want to check (numeric) input for a list of ranges (min, max), while input is partially entered; in other words, I need an elegant algorithm to check the number prefix against the range (without using regular expressions).

Examples of test boxes:

1 is in ( 5, 9) -> false 6 is in ( 5, 9) -> true 1 is in ( 5, 11) -> true (as 10 and 11 are in the range) 1 is in ( 5, 200) -> true (as eg 12 and 135 are in the range) 11 is in ( 5, 12) -> true 13 is in ( 5, 12) -> false 13 is in ( 5, 22) -> true 13 is in ( 5, 200) -> true (as 130 is in the range) 2 is in (100, 300) -> true (as 200 is in the range) 

Do you have any ideas?

Answer 1

I believe that entry is permissible if and only if:

• This is a prefix substring of the lower bound converted to a string

or

• Input followed by any number of extra zeros (possibly not) falls into the range

The first rule is required, for example, 13 is in range (135, 140) . The second rule is required, for example, 2 is in range (1000, 3000) .

The second rule can be effectively checked by a series of multiplications by 10, until the scaled input exceeds the upper limit.

Answer 2

Iterative wording:

 bool in_range(int input, int min, int max) { if (input <= 0) return true; // FIXME handle negative and zero-prefixed numbers int multiplier = 1; while ((input + 1) * multiplier - 1 < min) // min <= [input]999 multiplier *= 10; // TODO consider overflow return input * multiplier <= max; // [input]000 <= max } 

Simpler [edit: and more efficient; see below] the method is to use truncated integer division:

 bool in_range(int input, int min, int max) { if (input <= 0) return true; while (input < min) { min /= 10; max /= 10; } return input <= max; } 

---

Testing and profiling:

 #include <iostream> #include <chrono> bool ecatmur_in_range_mul(int input, int min, int max) { int multiplier = 1; while ((input + 1) * multiplier - 1 < min) // min <= [input]999 multiplier *= 10; // TODO consider overflow return input * multiplier <= max; // [input]000 <= max } bool ecatmur_in_range_div(int input, int min, int max) { while (input < min) { min /= 10; max /= 10; } return input <= max; } bool t12_isInRange(int input, int min, int max) { int multiplier = 1; while(input*multiplier <= max) { if(input >= min / multiplier) return true; multiplier *= 10; } return false; } struct algo { bool (*fn)(int, int, int); const char *name; } algos[] = { { ecatmur_in_range_mul, "ecatmur_in_range_mul"}, { ecatmur_in_range_div, "ecatmur_in_range_div"}, { t12_isInRange, "t12_isInRange"}, }; struct test { int input, min, max; bool result; } tests[] = { { 1, 5, 9, false }, { 6, 5, 9, true }, { 1, 5, 11, true }, // as 10 and 11 are in the range { 1, 5, 200, true }, // as eg 12 and 135 are in the range { 11, 5, 12, true }, { 13, 5, 12, false }, { 13, 5, 22, true }, { 13, 5, 200, true }, // as 130 is in the range { 2, 100, 300, true }, // as 200 is in the range { 13, 135, 140, true }, // Ben Voigt { 13, 136, 138, true }, // MSalters }; int main() { for (auto a: algos) for (auto t: tests) if (a.fn(t.input, t.min, t.max) != t.result) std::cout << a.name << "(" << t.input << ", " << t.min << ", " << t.max << ") != " << t.result << "\n"; for (auto a: algos) { std::chrono::time_point<std::chrono::system_clock> start = std::chrono::system_clock::now(); for (auto t: tests) for (int i = 1; i < t.max * 2; ++i) for (volatile int j = 0; j < 1000; ++j) { volatile bool r = a.fn(i, t.min, t.max); (void) r; } std::chrono::time_point<std::chrono::system_clock> end = std::chrono::system_clock::now(); std::cout << a.name << ": " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count() << '\n'; } } 

Surprisingly (at least for me) re-division comes out faster:

 ecatmur_in_range_mul: 17331000 ecatmur_in_range_div: 14711000 t12_isInRange: 15646000 

Answer 3

 bool isInRange(int input, int min, int max) { int multiplier = 1; while(input*multiplier <= max) { if(input >= min / multiplier) return true; multiplier *= 10; } return false; } 

It transfers all your test files.

Answer 4

One trivial solution is to create all the N-digit prefixes in the range. So, for 11 is in ( 5, 12) you need two-digit prefixes of all numbers from 5 to 12. Obviously, there are only 10, 11 and 12.

In the general case, for numbers from X to Y, possible N-bit prefixes can be obtained using the following algorithm:

 X = MIN(X, 10^(N-1) ) ' 9 has no 2-digit prefix so start at 10 Y = Y - (Y MOD 10^N) ' 1421 has the same 2 digit prefix as 1400 WHILE (X < Y) LIST_PREFIX += PREFIX(N, X) ' Add the prefix of X to the list. X += 10^(TRUNCATE(LOG10(X)) - N+1) ' For N=2, go from 1200 to 1300 

Answer 5

 (input >= lower_bound) && input <= upper_bound OR (f(input) >= lower_bound) && (f(input) <= upper_bound) OR (lower_bound - f(input) < pow(10, n_digits_upper_bound - n_digits_input)) && (lower_bound - f(input) > 0) where f(input) == (input * pow(10, n_digits_upper_bound - n_digits_input)) 1 is in ( 5, 9) -> 1 * pow(10,0) -> same -> false 6 is in ( 5, 9) -> true 1 is in ( 5, 11) -> 1 * pow(10,1) -> 10 is in (5,11) -> true 1 is in ( 5, 200) -> 1 * pow(10,2) -> 100 is in (5, 200) -> true 11 is in ( 5, 12) -> true 13 is in ( 5, 12) -> 13 * pow(10,0) -> same -> false 13 is in ( 5, 22) -> true 13 is in ( 5, 200) -> true 2 is in (100, 300) -> 2 * pow(10,2) -> 200 is in (100,300) -> true 4 is in (100, 300) -> 4 * pow(10,2) -> 400 is in (100,300) -> false 13 is in (135, 140) -> 135 - 130 -> true 14 is in (135, 139) -> 135 - 140 -> false 

Answer 6

I prefer an approach that uses already implemented algorithms. While many other solutions use recursive divisions by 10 , I think it's better to use logarithms with 10 points that have O(1) complexity, so the complexity of the whole solution is O(1) .

We divide the task into two parts.

The first part will handle the case when number * 10^n is between min and max for at least one n . This would allow us to check, for example, if number = 12 and min,max = 11225,13355 , that x = 12000 = 12*10^3 is between min and max . If this test is checked, it means that the result is True .

The second part will handle cases when number starts with either min or max . For example, if number = 12 and min,max = 12325,14555 , the first test will fail, because 12000 not between min and max (as well as all other numbers 12*10^n for all n ). But the second test will find that 12 is the beginning of 12325 and returns True .

First

Check if the first x = number*10^n , which is equal to or greater than min , is less than or equal to max (so min <= x <= max, where x is number*10^n for any integer n ). If it is greater than max , than all the other x es will be larger, since we took the smallest.

 log(number*10^n) > log(min) log(number) + log(10^n) > log(min) log(number) + n > log(min) n > log(min) - log(number) n > log(min/number) 

To get the number for comparison, we simply calculate the first satisfactory n :

 n = ceil(log(min/number)) 

And then calculate the number x :

 x = number*10^n 

Second

We must check whether our number is the literal beginning of any boundary.

We simply compute x , starting with the same digits as number , and padding 0 at the end, having the same length as min :

 magnitude = 10**(floor(log10(min)) - floor(log10(number))) x = num*magnitude 

And then check if the difference between min and x (on the scale scale) is less than 1 and greater than or equal to 0 :

 0 <= (min-x)/magnitude < 1 

So if number 121 and min is 132125 , then magnitude is 1000 , x = number*magnitude will be 121000 . min - x gives 132125-121000 = 11125 , which should be less than 1000 (otherwise the start of min would be more than 121 ), so we compare it with magnitude by dividing by this value and comparing with 1 , And that's fine if min - 121000 but not OK if min is 122000 , so 0 <= and < 1 .

The same algorithm for max .

Pseudo code

Including all of this in pseudo-code gives this algorithm:

 def check(num,min,max): # num*10^n is between min and max #------------------------------- x = num*10**(ceil(log10(min/num))) if x>=min and x<=max: return True # if num is prefix substring of min #------------------------------- magnitude = 10**(floor(log10(min)) - floor(log10(num))) if 0 <= (min-num*magnitude)/magnitude < 1: return True # if num is prefix substring of max #------------------------------- magnitude = 10**(floor(log10(max)) - floor(log10(num))) if 0 <= (max-num*magnitude)/magnitude < 1: return True return False 

This code can be optimized by avoiding the re-calculation of log10(num) . In addition, in the final solution, I would go from float to an integer region ( magnitude = 10**int(floor(log10(max)) - floor(log10(num))) ), and then perform all comparisons without division, i.e. e. 0 <= (max-num*magnitude)/magnitude < 1 → 0 <= max-num*magnitude < magnitude . This would facilitate the possibility of rounding errors.

In addition, it may be possible to replace magnitude = 10**(floor(log10(min)) - floor(log10(num))) with magnitude = 10**(floor(log10(min/num))) , where log10 calculated just one time. But I cannot prove that he will always give the correct results, and I cannot refute it. If anyone could prove it, I would be very grateful.

_{Tests (in Python): http://ideone.com/N5R2j (you can edit input to add other tests).}

Answer 7

Given the value of n, start with the half-open range [n, n + 1) and continue by orders of magnitude:

• [10 n , 10 (n + 1))
• [100 n , 100 (n + 1))
• [1000 n , 1000 (n + 1))
• ...

Continue until the repeating range overlaps the target range or the two ranges can no longer overlap.

 #include <iostream> bool overlaps(int a, int b, int c, int d) { return a < c && c < b || c < a && a < d; } bool intersects(int first, int begin, int end) { int last = first + 1; ++end; while (first <= end) { if (overlaps(first, last, begin, end)) return true; first *= 10; last *= 10; } return false; } int main(int argc, char** argv) { std::cout << std::boolalpha << intersects( 1, 5, 9) << '\n' << intersects( 6, 5, 9) << '\n' << intersects( 1, 5, 11) << '\n' << intersects( 1, 5, 200) << '\n' << intersects(11, 5, 12) << '\n' << intersects(13, 5, 12) << '\n' << intersects(13, 5, 22) << '\n' << intersects(13, 5, 200) << '\n' << intersects( 2, 100, 300) << '\n' << intersects(13, 135, 140) << '\n'; } 

The use of ranges is necessary to prevent missing cases. Consider n = 2 and the target range [21, 199]. 2 is not in the range, so we multiply by 10; 20 is not in the range, so again we multiply by 10; 200 is not in the range or does not have a larger number, so the naive algorithm ends with a false negation.

Answer 8

I came up with this new simple solution, thinking about the proof for @Ben Voigt's beautiful solution:

Let's go back to elementary school, where we made a comparison of numbers. The question will be: check if the number "A" is in the range of the number "B" and the number "C"

Solution: add the necessary zeros to the left side of the numbers (so that we have an equal number of digits in all numbers). We start with the leftmost digit. compare it with the equivalent number in the other two numbers.

• if a digit from A is less than a digit from B or more than a digit from C, then A is not in the range.

• if we do not repeat the process with the next digit from A and the equivalents from B and C.

IMPORTANT QUESTION: Why don't we stop right now? Why are we checking the following numbers?

IMPORTANT ANSWER: Since the figure from A is between the equivalents from B and C, is OK so far , but there are still not enough reasons to make a decision! (obviously right?)

This, in turn, means that there may be a set of numbers that could bring A out of range.

And, LIKEWISE

There may be a set of numbers that can put A within a range

, which is another way of saying that A can be a prefix of a number in a range.

Isn't that what we were looking for?!: D

The basis of the algorithm will be basically a simple comparison for each input event:

• Add a zero (if necessary) to the left of min so that the length of min and max becomes equal.
• compare input A with equivalent digits from min and max (cut the corresponding digits min and max from left and wrong )
• Input A <= corresponding part max AND > = corresponding part min? (no: return false, yes: return true)

false and true here express the situation “so far” as the problem requires.

Answer 9

All severe cases are situations in which the lower bound has fewer digits than the upper bound. Just break the range into two (or three). If AB is the union of the sets A and B, then x in A or x in B follows from x in AB . So:

13 is in (5, 12) => 13 is in (5, 9) OR 13 is in (10, 12)

13 is in (5, 120) => 13 is in (5, 9) OR 13 is in (10, 99) OR 13 is in (100, 120)

Then trim to fit lengths. I.e.

13 is in (5, 120) => 13 is in (5, 9) OR 13 is in (10, 99) OR 13 is in (10 0 , 12 0 )

After this second rewriting, it becomes a simple numerical check. Please note that if you have a range of 10,99 , then you have all the possible two-digit prefixes and you really don't need to check, but this is an optimization. (I assume we ignore 00-09 prefixes)

Answer 10

Yes, another answer. To enter X and MIN and MAX boundaries

 WHILE (X < MIN) IF X is a prefix of MIN x = 10*x + next digit of MIN ELSE x = 10*x RETURN (x>= MIN && x<=MAX) 

This works by “typing” the next lower digit. Thus, the hard case 13 in (135, 140) adds 5 to produce 135, not zero.

Answer 11

Regardless of the implementation method you choose, you should consider creating many unit tests. Because you ask the question the same way you would write a test for test development (TDD). Therefore, I suggest that while you expect a suitable algorithm to come out, write your unit tests:

Make the test unsuccessful if the examples you provide do not give results in your examples. To be sure, write a couple of other tests. Then, if you use the wrong or erroneous algorithm, you will find out soon. Once your test passes, you will know that you have reached your goal.

In addition, it protects you from any regression in the future.

Answer 12

Maybe I'm thinking too much about it, but assuming the Min-Max integer range is all positive (that is, greater than or equal to zero), this block code should do the trick nicely:

 bool CheckRange(int InputValue, int MinValue, int MaxValue) { // Assumes that: // 1. InputValue >= MinValue // 2. MinValue >= 0 // 3. MinValue <= MaxValue // if (InputValue < 0) // The input value is less than zero return false; // if (InputValue > MaxValue) // The input value is greater than max value return false; // if (InputValue == 0 && InputValue < MinValue) return false; // The input value is zero and less than a non-zero min value // int WorkValue = InputValue; // Seed a working variable // while (WorkValue <= MaxValue) { if (WorkValue >= MinValue && WorkValue <= MaxValue) return true; // The input value (or a stem) is within range else WorkValue *= 10; // Not in range, multiply by 10 to check stem again } // return false; } 

Answer 13

OK, a little late for the party, but here goes ...

Note that this is about user input, so this is not enough for // TODO: consider overflow . Confirming user input is war, and cutting corners will ultimately lead to detonation of the IED. (Well, well, maybe not so dramatic, but still ...) In fact, only one of the algorithms of the useful ecatmur test harness correctly processes the angle register ( {23, 2147483644, 2147483646, false} ), and the test itself the wiring goes into an infinite loop if t.max too large.

The only one that went through was ecatmur_in_range_div, which I think is pretty nice. However, you can do this (slightly) faster by adding a few checks:

 bool in_range_div(int input, int min, int max) { if (input > max) return false; if (input >= min) return true; if (max / 10 >= min) return true; while (input < min) { min /= 10; max /= 10; } return input <= max; } 

How much faster it "depends"; it would be especially useful if min and max were compile time constants. I think the first two tests are obvious; the third can be proved in various ways, but the simplest is just to observe the behavior of the ecatmur cycle: when the circuit ends, the input signal => min, but <10 * min, so if 10 * min <max, the input should be less than max.

The expression of arithmetic in terms of division rather than multiplication should be a habit; I know that most of us have grown up with the idea that separation is sloooooow and should be avoided. However, division, unlike multiplication, will not overflow. Indeed, whenever you write:

 if (a * k < b) ... 

or

 for (..., a < b, a *= k) 

or other variations of these topics, you should immediately mark this as an integer overflow and change it to an equivalent division.

Actually, the same applies to the addition, except for one important (but general) case:

 if (a + k < b) ... 

or

 a += k; if (a < b) ... 

also unsafe if k is not one, and you know that a <b before adding. This exception allows the normal cycle to work without too much thought. But watch out for this, which I used as part of the interview question:

 // enumerate every kth element of the range [a, b) assert(a < b); for (; a < b; a += k) { ... } 

Unfortunately, very few candidates received it.

Answer 14

Now I will delete this answer, except that it shows an unsuccessful approach.

After checking Str(min).StartWith(input) you need to check numerically if any 10^n*Val(input) is within the range, as the current Ben Voight answer says.

---

Unsuccessful attempt

Edited due to Ben Voigt's comment: (I missed my first paragraph in his current answer: the minimum matches to the minimum are fine.)

My @Ben Voigt knowledge-based solution checks if Min StartsWith current input. If not, PadRight current input from 0 to Max length as a string. Then, if this modified input is lexically (i.e., treated as strings) between Min and Max , it is OK.

Pseudocode:

  Confirm input has only digits, striping leading 0s (most easily done by converting it to an integer and back to a string) check = Str(min).StartsWith(input) If Not check Then testInput = input.PadRight(Len(Str(max)), '0') check = Str(min) <= testInput && testInput <= Str(max) End If 

Answer 15

 int input = 15; int lower_bound = 1561; int upper_bound = 1567; int ipow = 0; while (lower_bound > 0) { if (lower_bound > input) { ++ipow; lower_bound = lower_bound / 10; } else { int i = pow(10, ipow) * input; if (i < upper_bound) { return true; } return false; } } return false;