Sunday, January 25, 2015

Page Number

Question: 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' occurs 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

Idea: Brute force. Start from 1, accumulate the number of d's appearance. At the first accumulated appearance==k, update the lower bound; at the last appearance==k, update the upper bound.

Time: O(k) Space: O(1)

Code:
 public class PageNumber {  
      public PageNumber()  
      {  
           int[] test1=pageNumber(4,1);  
           printArray(test1);  
           int[] test2=pageNumber(4,0);  
           printArray(test2);  
      }  
      public void printArray(int[] array)  
      {  
           for(int i:array)  
           {  
                System.out.print(i);  
                System.out.print(' ');  
           }  
           System.out.println("\n");  
      }  
      public int[] pageNumber(int d,int k)  
      {  
           int[] result={Integer.MIN_VALUE,Integer.MIN_VALUE};  
           int i=1;  
           char target=(char)(d+'0');  
           int counter=0;  
           while(counter<=k)  
           {  
                String s=Integer.toString(i);  
                for(char c:s.toCharArray())  
                {  
                     if(c==target)  
                          counter+=1;  
                }  
                if(result[0]==Integer.MIN_VALUE&&counter==k)  
                     result[0]=i;  
                if(counter==k)  
                     result[1]=i;  
                i++;  
           }  
           return result;  
      }  
 }  

No comments:

Post a Comment