Write Code vs. Write Poetry: 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)
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)
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;
} 