A book contains with pages nu... | CareerCup

A book contains with pages nu... | CareerCup
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 occurences 'k' of certain digit 'd' in this string. 

For example, let N=12, d=1, hence 

s = '123456789101112' => k=5 

since digit '1' occure five times in that string. 

Problem: Write a method that, given a digit 'd' and number of its occurences '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

int count(int n, int d){
  int res=0;
  while(n){
    if(n%10==d)
      ++res;
    n=n/10;
  }
  return res;
}

pair<int,int> bookPage(int d, int k){
  pair<int,int> res;
  int i=1, cnt=0;
  while(cnt<k){
    cnt+=count(i,d);
    ++i;
  }
  res.first=i==1?1:i-1;
  while(count(i,d)==0)
    ++i;
  res.second=i-1;
  return res;
}

public class DigitOccurrance {
 public static void main (String [] args) {
  int d = 6;
  int k = 501;
  int max = 0;
  int numOfDigits = getNumOfDigits(k);
  int lastMax = 0;
  for (int i = 0; i < numOfDigits; i++) {
   lastMax = max;
   max = max * 10 + 9;
  }
  System.out.println(max);
  System.out.println("The desired num = " + findNum(lastMax + 1, max, d, k, numOfDigits));
 }

 public static int findNum(int start, int end, int d, int k, int numOfDigits) {

  int mid = (start + end) / 2;
  System.out.println("Calling for start = " + start + " end = " + end);

  int midNumOfOccurrances = getNumOfOccurrances(mid, d, numOfDigits);
  if (start == end) {
   if (midNumOfOccurrances == k) {
    return mid;
   }
   else {
    System.err.println("Wrong input!");
    System.exit(1);
   }
  }
  if (midNumOfOccurrances < k) {
   return findNum(mid + 1, end, d, k, numOfDigits);
  }
  else {
   return findNum(start, mid, d, k, numOfDigits);
  }
 }

 public static int getNumOfOccurrances(int num, int digit, int numOfDigits) {
  int [] array = new int[numOfDigits];
  int count = 0;
  for (int i = 0; i < numOfDigits; i++) {
   int x = (int)(num / Math.pow(10, i)) % 10;
   count = x * i * (int)Math.pow(10, i - 1);
   if (i > 0) {
    count += array[i - 1];
   }
   else {
    count = 0;
   }
   if (x == digit) {
    count += num % Math.pow(10, i);
   }
   if (x > digit) {
    count += Math.pow(10, i);
   }
   array[i] = count;
  }
  return count;
 }

 // Given k, we establish a upper limit on the required number.
 public static int getNumOfDigits(int k) {
  if (k == 0) {
   return 0;
  }
  int n = 1;
  while (n * Math.pow(10, n - 1) < k) {
   n++;
  }
  return n;
 }

Read full article from A book contains with pages nu... | CareerCup