Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits but xxx11 < 54432 should hold.

What is count of all the numbers of form x11xx and x11xx < 54432 ?

How to solve this in general and fast way i.e any number other than 1 , say y and arbitrary position of two contiguous digits as y and count of all such numbers less than a given integer.

can we solve this problem using strings ?

Like for 54411 , total count is 545 . Just remove 11 part and add 1. for 54112 ,total count is 543 , just remove 11 part .


1 Answer 1


So say you want to count all numbers of the form $x_1\cdot ab\cdot x_2$ less than $n$, where $x_1$ and $x_2$ are numbers with a fixed number of digits, and $ab$ are two contiguous digits.

Cut $n$ in the same positions as your $x_1\cdot ab \cdot x_2$ pattern to get $n_1\cdot pq\cdot n_2$.

Now when is $x_1\cdot ab\cdot x_2 < n_1\cdot pq\cdot n_2$?

  • Either $x_1 < n_1$, then any choice for $x_2$ goes. I.e., $10^{\text{number-of-digits}(x_2)}$ choices for $x_2$ whenever $x_1<n_1$. In total you get $n_1\times10^{\text{number-of-digits}(x_2)}$ choices for this case, or $(n_1-10^{\text{number-of-digits}(x_1)-1})\times10^{\text{number-of-digits}(x_2)}$ choices if you don't allow for leading zeros.
  • Or $x_1=n_1$, in which case it depends on $ab$ and $pq$.
    • If $ab<pq$ then any choice for $x_2$ goes, so you get an additional $10^{\text{number-of-digits}(x_2)}$ choices.
    • If $ab=pq$ then you have to have $x_2<n_2$ which gives you an additional $n_2$ choices.
    • If $ab>pq$ then no choice of $x_2$ will work.

In short, with leading zeros allowed:

  • If $ab<pq$ : $$n_1\times10^{\text{number-of-digits}(x_2)} + 10^{\text{number-of-digits}(x_2)}$$
  • If $ab=pq$ : $$n_1\times10^{\text{number-of-digits}(x_2)} + n_2$$
  • If $ab>pq$ : $$n_1\times10^{\text{number-of-digits}(x_2)}$$

For example with $x11xx$ and $54432$ you get: $$5\times 10^2 + 10^2 = 600$$

  • $\begingroup$ Your answer is wrong . because for x11xx 54432 , your answer is 600 .But then x11xx 54421 also your answer will be 600 which is not possible since for 54421 it should be less .BTW answer for x11xx is 533 . Is it trivial to see . $\endgroup$
    – user108281
    Aug 6, 2019 at 15:14
  • $\begingroup$ Why would it be less for x11xx 54421 than for x11xx 54432? Can you show me a number that works for x11xx 54432 but not for x11xx 54421? Also, a brute-force approach confirms that the answer is 600 for x11xx 54432. Just run the following python code if you don't believe me: tot = 0 for x in range(54432): s = str(x) if (len(s)>=4 and (s[-4:-2] == '11')): tot += 1 print(tot) (you'll have to redo the indenting and formatting, I can't post it correctly in the comments). $\endgroup$
    – Tassle
    Aug 6, 2019 at 15:39
  • $\begingroup$ Sorry Tassle , you are right . Are there any corner cases .You did not talked about situations when 11 is in last position or first position i.e $x_1⋅ab<n_1⋅pq$ $\endgroup$
    – user108281
    Aug 6, 2019 at 16:03
  • $\begingroup$ If I'm not mistaken It should also work in corner cases. In the example you give you just have to consider that $number−of−digits(x_2) = 0$ and $n_2 = 0$ in the formulas. The only special case is if $x_1$ is empty and you don't allow for leading zeros. In that case you can just skip the first part of the formula completely. (Also, please don't say things like "It is trivial to see" when you think someone is wrong, it can be considered quite disrespectful) $\endgroup$
    – Tassle
    Aug 6, 2019 at 16:11
  • $\begingroup$ I am Sorry for that :) $\endgroup$
    – user108281
    Aug 6, 2019 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.