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