Monday, February 23, 2015

Number of pages in a book

A book contains with pages numbered from 1 - N. Imagine now that you concatenate all page numbers in the book such that you obtain a sequence of numbers which can be represented as a string.
You can compute number of occurrences 'k' of certain digit 'd' in this string.
For example, let N=12, d=1, hence
s = '123456789101112' => k=5
since digit '1' occur five times in that string.

Problem: Write a method that, given a digit 'd' and number of its occurrences 'k', returns a number of pages N. More precisely, return a lower and upper bound of this number N.
Example:
input: d=4, k=1;
output {4, 13} - the book has 4-14 pages
input d=4 k=0;
output {1, 3} - the book has 1-3 pages
 I don't consider my solution is the most efficient one, but it is reasonable, and at least, correct.

For every 100 pages, or more precisely, 0 - 99 (100 - 199, ...) pages, there exists 20 occurrences of any digit d, except for 0 for (0 - 99 pages), there are only 9,  because there is no 0 from 0 - 9 pages. So the first step is to calculate how many hundreds of pages in the book.

hundreds = k / 20;

Next, we want to know how many d's left in tens. This is done by mod k by 20;

tens = k % 20;

If tens = 6, then there are 6 ds in (0 - 99) pages, or (hundreds * 100, hundreds * 100 + 99) pages.

Now we have the tricky part. Let's take d = 7as an example.

If tens = 0, then it is easy, the range of the pages will include all d's in one hundred pages.

(hundreds - 1) * 100 + 90 + d, range[0] + 10 - 1)

Take 7 as an example, if k = 20, then the range is
(97, 106).
Note we need to decrement hundreds by 1 when tens = 0.

If tens != 0, we will have different cases. Note that we will have d of ds if  tens (the second digit in the page number) is less than d. Then we will have 11 ds from d * 10 to d * 10 + 9. Then we will have another 9 - d ds after that.
If d = 7, we will have 7 7s from 0 - 69, 11 7s from 70 - 79 and another 2 ds from 80 - 99. Thus we need to calculate ranges based on different situations.

If tens < d,


range[0] = hundreds * 100 + (tens - 1) * 10 + d;
range[1] = range[0] + 10 - 1;

d = 7, k = 25 -> hundreds = 1, tens = 5
(147, 156)

If tens = d
we have to exclude d * 10 to d * 10 + d - 1
so 

range[0] = hundreds * 100 + (tens - 1) * 10 + d;
range[1] = hundreds * 100 + (tens - 1) * 10 + 9;

d = 7, k = 27 ->  hundreds = 1, tens = 7
(167, 169)

Now if tens > d, let dInTens, which is the number of ds from ( d * 10,  d * 10 + 9) = tens - d

start from the easier one, if dInTens > 11, then the range must be from (d + 1) * 10 - 99, for d = 7, it is 80 - 99

range[0] = hundreds * 100 + (tens - 11) * 10 + d;
range[1] = range[0] + 10 - 1;

d = 7, k = 39 -> hundreds = 1, tens = 19
range (187, 196)

if dInTens < 11, then we are in the range d * 10 to d * 10 + 8. In this situation, increment any page will increase k, thus the range is an exact number. Moreover, when the single digit equals to d, we will have 2 ds. 


If dInTens <= d, then the range is from d * 10 to d * 10 + d - 1. 
For d = 7, k = 13 -> tens = 13, dInTens = 6, the range is (70, 76), more precisely, 

range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 1;

so (75, 75)

If dInTens > d, then 

range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 2;

Because d* 10 + d takes 2 ds. 
For d = 7, k = 17 -> tens = 17, dInTens = 10, range (77, 77)

Now we have one more situation, where dInTens = 11, we are in the range ( d * 10 + 9, d * 10 + 9 + d). Because the next d will occur when the next single digit = d. 

range[0] = hundreds * 100 + d * 10 + 9;
range[1] = range[0] + d;

for d = 7, k = 18 -> tens = 18, dInTens = 11, range (79, 96)


I know the explanation looks tedious. Honestly I am also looking for a more concrete code. 




public class NumberOfPages {
 public static int[] pages(int d, int k) {
  if (d < 0 || k < 0)
   throw new IllegalArgumentException("pages must be non negative!");
  int[] range = new int[2];
  if (k == 0) {
   if (d == 1)
    range[0] = range[1] = 0;
   else {
    range[0] = 1;
    range[1] = d - 1;
   }
   return range;
  }
  //the number of hundreds of pages
  int hundreds = k / 20;
  if (d == 0) {
   hundreds = k > 9 ? ((k - 9) / 20) + 1 : 0;
  }
  //the number of d's from 0 - 99 pages
  int tens = k % 20;
  if (tens == 0) {
   range[0] = (hundreds - 1) * 100 + 90 + d;
   range[1] = range[0] + 10 - 1;
  }
  else if (tens - d  <= 0) {
   range[0] = hundreds * 100 + (tens - 1) * 10 + d;
   //System.out.println("range[0]: " + range[0]);
   if (tens - d  == 0) 
    range[1] = hundreds * 100 + (tens - 1) * 10 + 9;
   else
    range[1] = range[0] + 10 - 1;
   //System.out.println("range[1]: " + range[1]);
  }
  else {
   int dInTens = tens - d;
   if (dInTens > 11) {
    range[0] = hundreds * 100 + (tens - 11) * 10 + d;
    range[1] = range[0] + 10 - 1;
   }
   else {
    if (dInTens <= d)
     range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 1;
    else if (dInTens == 11) {
     range[0] = hundreds * 100 + d * 10 + 9;
     range[1] = range[0] + d;
    }
    else 
     range[0] = range[1] = hundreds * 100 + d * 10 + dInTens - 2;
   }
  }
  return range;
 }

 public static void main(String[] args) {
  for (int k = 0; k <= 20; k++) {
   for (int i : pages(7, k))
    System.out.print(i + " ");
   System.out.println();
  }
  for (int i : pages(7, 18))
   System.out.print(i + " ");
 }

}


1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete