Google Interview Question
Country: United States
C# implementation
class OccurrenceOfKInNumber1ToN
{
/// <summary>
/// Finds the page boundaries that the digit is shown in given occurrence times.
/// </summary>
/// <param name="digit">Number to be found.</param>
/// <param name="occurrence">Target occurrence.</param>
/// <param name="begin">Left boundary of result page range.</param>
/// <param name="end">Right boundary of result page range.</param>
public static void GetPageRangeForGivenOccurrenceOfDigitAndPageBoundary(int digit,int occurrence, out int begin, out int end)
{
GetPageBoundaryIncludingOccurrence(digit, occurrence, out begin, out end);
begin = BinarySearch(begin, end, digit, occurrence, isLeftBoundary: true);
end = BinarySearch(begin, end, digit, occurrence, isLeftBoundary: false);
}
/// <summary>
/// Get a page range [A,B] in which for any number N with CheckOccurrence(N,digit) == occurrence, A<=N<=B
/// </summary>
/// <param name="digit">Number to check occurrence.</param>
/// <param name="occurrence">Target occurrence.</param>
/// <param name="begin">Left boundary of result page range.</param>
/// <param name="end">Right boundary of result page range.</param>
/// <returns>True if found a range, otherwise, false.</returns>
private static void GetPageBoundaryIncludingOccurrence(int digit, int occurrence, out int begin, out int end)
{
begin = 1;
end = 1;
// This can cause overflow, here just throw exception.
while (end <= int.MaxValue)
{
int o = CheckOccurrence(end, digit);
if (o == occurrence)
{
end *= 2;
}
else if (o > occurrence)
{
break;
}
else
{
begin = end + 1;
end *= 2;
}
}
}
/// <summary>
/// Binary search to find the left or right boundary of occurrence of digit
/// </summary>
/// <param name="begin">Left boundary to search</param>
/// <param name="end">Right boundary to search</param>
/// <param name="digit">Number to check occurrence.</param>
/// <param name="occurrence">Target occurrence.</param>
/// <param name="isLeftBoundary">True if finding left boundary, otherwise, right boundary.</param>
/// <returns>result.</returns>
private static int BinarySearch(int begin, int end, int digit, int occurrence, bool isLeftBoundary)
{
int last = -1;
while (begin <= end)
{
// prevent overflow
int mid = begin + (end - begin) / 2;
int o = CheckOccurrence(mid, digit);
if (o == occurrence)
{
last = mid;
if (isLeftBoundary)
{
end = mid - 1;
}
else
{
begin = mid + 1;
}
}
else if (o > occurrence)
{
end = mid - 1;
}
else
{
begin = mid + 1;
}
}
return last;
}
/// <summary>
/// Get the occurrence of k in every digits of numbers 1 - n
/// </summary>
/// <param name="n">Numbers upper bundary</param>
/// <param name="d">A number to check occurrence (0<k<10)</param>
/// <returns></returns>
public static int CheckOccurrence(int n, int d)
{
int t = 1, count = 0;
int m = n;
// Assume m = ABC now
while (m > 0)
{
// Check all occurrence of d in last digit from 0 - (AB-1)(9...)
count += m / 10 * t;
// if k is 0 then don't count this cuz we don't count 0C.
if (d != 0)
{
// If C > k then we need to add all occurrence of d in last digit from ABK(0...) - ABK(9...) )
if (m % 10 > d)
{
count += t;
}
// If C == K, assume n = ABCY then the occurnece of d in last digit from AB0(0...) - ABKY is Y
else if (m % 10 == d)
{
count += n % t + 1;
}
}
m /= 10;
t *= 10;
}
return count;
}
}
For digit = 3 , let no of occurences k = 32
Precalculated
1. number of occurences of 3 from 0-9, f(10) = 1
2. number of occurences of 3 from 0-99, f(100) = f(10) * 10 + 10 = 20
algo :
if( k > 0 ) {
1. k++
2. H = k/f(100) = 33/20 = 1
3. k = k - H*f(100) = k - 1*20 = 33 - 20 = 13
4. last_number = 0;
for( i = 0 ; i <= 9 ; i++) {
if(digit == i)
if( k-10 < 0){
break;
}
else
k = k - 10;
}
if( k > 0 ){
k--;
}
else
break;
}
last_number = H*100 + 10 * (i+1) + d;
5. from = d ; to = last_number-1
}
else{
from = 0 ; to = d -1;
}
@root545 - here i'm calculating total number of digits between 0 to n numbers .
say digit 1 comes 1 time between 0-9 hence f(10) = 1 , and between 0-99 it came for about 20 times hence f(100) = 20.
now for total occurrences given , let say k = 32, we'll calculate the maximum digit till when we'll get k = 32 ie. 0 to max_digits contains exactly 32 occurrences of 1.
Now for minimum digit for sure it will lie in 0-9 range only, for d = 1 minim_digit = 1.
Accordingly , for k = 0 , we'll calculate where the first occurrence of digit starts, so range would be min_digit = 0 , max_digit = d-1
Your answer is incorrect. Your base calculation is wrong: number of occurences of 3 from 0-99 is 19 not 20. 30-39 = 10 + (03, 13, 23,(NOT 33, we already counted that in 30-39), 43, 53, 63, 73, 83, 93) 9 = 19.
Not the most efficient code, but it's the easiest to implement and explain:
basically loop until you reach the integer that has k counts of the digit before it. record it as the beginning of your possible range. then, find the next integer that produces a count of digits before it that exceeds k, find the number right before that and set it as the ending of the possible range
public int[] range(int d, int k) {
int[] range = new int[2];
int count = 0;
int i = 0;
while (true) {
int temp = numPresent(i, d);
if (temp > 0 && count <= k ) {
count += temp;
range[0] == i;
}
if (temp > 0 && count > k ) {
count += temp;
range[1] == i-1;
break;
}
i++;
}
return range;
}
int numPresent(int n, int digit) {
//returns the number of digit in the integer n
}
The easiest way is just to iterate from page 1 to the max page allowed, when the occurrence of d is equal to k, record the min and max pages.
vector<int> calcBound(int d, int k) {
vector<int> res(2);
int it = 0;
int N = 1;
int N1 = N;
int minBound = INT_MAX;
int maxBound = INT_MIN;
while (it <= k) {
N1 = N;
while (N1 > 0) {
if (N1 % 10 == d) it++;
N1 = N1 / 10;
}
if (it == k) {
minBound = min(minBound, N);
maxBound = max(maxBound, N);
}
else if (it > k) break;
N++;
}
res[0] = minBound;
res[1] = maxBound;
return res;
}
protected int[] getPageNumberRange(int d, int k)
{
int[] arr = new int[2];
arr[0] = d;
if(d == k)
{
arr[1] = 11*d - 10;
}
else
{
arr[1] = d + (10*k) - 10;
}
return arr;
}
protected int[] getPageNumberRange(int d, int k)
{
int[] arr = new int[2];
arr[0] = d;
if(d == k)
{
arr[1] = 10d - 1;
}
else
{
arr[1] = 10k + d - 1;
}
return arr;
}
/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
static int N = 15;
public static void findBound(int d,int k)
{
int index=1; int firstNine = 9;
int tenthPower = 1;
int count=k;
int lowerBound = (k == 1? 1:d),upperBound=0;
StringBuilder sb = new StringBuilder();
for(int i=1; i<N ;i++)
{
sb.append(i);
}
System.out.println(sb.toString());
char s[] = sb.toString().toCharArray();
int incPointer = 1;
int numMatch = 0;
for(int j=0,num=0;j<s.length;j++)
{
if( tenthPower == incPointer)
{
num++;
incPointer = 0;
}
if(j <= Math.pow(10,tenthPower))
{
int c = (int)(s[j]-'0');
//System.out.println(" c: "+c+" , d: "+d + ", j : "+j);
if(d == c)
{
numMatch = numMatch+1;
if(numMatch == count)
{
upperBound = num>10? num-1:num;
}
}
}
else
{
//System.out.println(" ~~~ j : "+j);
tenthPower = tenthPower+1;
int c = (int)(s[j]-'0');
//System.out.println(" c: "+c+" , d: "+d + ", j : "+j);
if(d == c)
{
numMatch = numMatch+1;
System.out.println(" match : "+numMatch + " num : "+num);
if(numMatch == count)
{
upperBound = num;
}
}
}
incPointer++;
}
System.out.println("{ "+lowerBound+": "+upperBound+"}");
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
findBound(4,2);
//findBound(1,2);
findBound(1,4);
//findBound(1,2);
}
}
Let Occurrence(d, k) returns a number in which digit d occurs k-th time, then the desired range is (Occurrence(d,k), Occurrence(d, k + 1)).
Also, the formula for total number of occurrence of any digit in all the n-digit numbers is given by n * 10^(n - 1).
Based on this two information, we can find the desired range.
Your formula appears incorrect for total occurrences of a single digit within all possible numbers with n digits. Assuming the digit is 1-9 it should be 1+9*1+9*10*1+...+9*10^(n-2)*1=1+9*sum(i=0,...,n-2 : 10^i)=1+9*(1-10^(n-1))/(1-10)=1+(10^(n-1)-1)=10^(n-1) if we count each digit location individually.
You applied the formula wrong, for a single(n = 1) digit number, the occurrence of any digit (0 to 9) is 1 * 10 ^ (0) = 1;
For a 2 digit number (10 to 99), occurrence = 2 * 10 = 20
For a 3 digit number (100 to 990), occurrence = 3 * 100 = 300 and so on. You should be able to easily verify this.
I have a doubt.
for d = 4,k =1
range could also be {1,4} but why the range has been specified as {4-13}
I think this question is not clear. can't understand the meaning of lower and upper bound.
For example, if d=4, k=1, lower and upper can also be {1, 4}?
It means you can get only one 4 in the page string, if you have highest page number = 4 (atleast)i.e s=1234(always the book starts from page number 1 and here k=1 means the number of occurrences of 4 in the page string i.e sequence of page numbers).
But at max you can have a book with highest page number = 13 and still get only one 4 in the page string as we have only 1 occurrence of the digit 4 in the string 12345678910111213.
void get_lower_upper_bound(int d, int k, int* lower, int* upper)
{
if (lower == NULL || upper == NULL) return;
int i;
*lower = -1;
*upper = -1;
int count = 0;
for (i = 1; i <= N; i++) {
int cur = i;
do {
if (cur % 10 == d) {
count++;
}
if (*lower == -1 && count == k) {
*lower = i;
} else if (*lower != -1 && count == k+1) {
*upper = MAX(*lower, i-1);
}
if (*lower != -1 && *upper != -1) {
return;
}
cur = cur / 10;
} while (cur > 0);
}
}
for digit d, the number of it occurrences in all number of length l is:
f(l) = f(l-1)*10 + 10**(l-1)
f(1) = 1
0 is special, we need do minus of case like:
0,01,02,03…
so for 0,
we minus:
sum(10**i) #i in [0,1,2,3 ,l-1]
So, now, we know occurrence number of d for books of:
10**i-1(i>1)
pages
Based on this,, we can further decide the occurrence number of d for any given number is a
nearly constant time, as shown by nonzero_cal and zero_cal.
calculation of zero can be a little tricky though.
This solution can deal with thick books fast,,, well, yeah,, there's no so thick books existing ever~
def validate(limit):
arr = [[]] * (limit+1)
for a in xrange(len(arr)):
arr[a] = [0] * 10
for i in xrange(1, limit+1):
p = i
while i > 0:
arr[p][i%10] += 1
i/=10
for j in xrange(10):
arr[p][j] += arr[p-1][j]
return arr
def nonzero_cal(num, n):
ds = len(str(num))
m = int(str(num)[0])
cnt = __cal(ds-1)
cnt *= m
if n < m:
cnt += 10**(ds-1)
next = num - m*(10**(ds-1))
if next < 10:
if next >= n:
cnt += 1
if m == n:
cnt += next
elif m == n:
cnt += next
cnt += nonzero_cal(next, n)
else:
cnt += nonzero_cal(next, n)
cnt += str(m*(10**(ds-1))).count(str(n))
return cnt
def zero_cal(num, first=True):
ds = len(str(num))
m = int(str(num)[0])
cnt = __cal(ds-1)
cnt *= m
cnt += 10**(ds-1)
#print cnt
if first:
for i in xrange(ds):
cnt -= 10**i
else:
cnt -= 1
next = num - m*(10**(ds-1))
#print next, cnt
if ds-len(str(next)) > 1:
cnt += next*(ds-1-len(str(next)))
# print cnt
if next >= 10:
cnt += zero_cal(next, False)
if first:
cnt += str(m*(10**(ds-1))).count('0')
#print cnt
return cnt
cache = validate(100)
def cal(num, n, flg=False):
if num < 100:
global cache
return cache[num][n]
if n == 0:
return zero_cal(num)
else:
return nonzero_cal(num, n)
#get ocurrences of n with numbers within length
def __cal(length):
if length == 1:
return 1
return __cal(length-1)*10+10**(length-1)
def solve(n, cnt):
page = 1
while cal(page, n) < cnt:
page *= 2
page = page/2
ds = len(str(page))
m = 10**(ds-1)
num = cal(page+m, n)
while num != cnt:
if num > cnt:
m /=10
num = cal(page+m, n)
else:
page += m
num = cal(page+m, n)
page = page + m
low,high = 0,0
t = page-1
while cal(t,n) == cnt:
t -= 1
low = t+1
t = page+1
while cal(t,n) == cnt:
t += 1
high = t-1
return low,high
if __name__ == '__main__':
'''
c = validate(5000)
for i in xrange(1, 5000):
for j in xrange(10):
if cal(i, j) != c[i][j]:
print "Miss ",i,j, cal(i,j), c[i][j]
raw_input()
'''
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;
}
}
Runnable C++ version
#include <iostream>
using namespace std;
int main()
{
const int N = 19;
const int d = 4;
const int k = 0;
int counter = 0;
int lmark = -1;
int rmark;
for(int i = 1; i<= N; i++)
{
if((i % 10) == d)
counter++;
if((i / 10) == d)
counter++;
if(lmark == -1)
if(counter == k)
lmark = i;
if(counter == k + 1)
{
rmark = i - 1;
break;
}
}
cout<<lmark<< ", "<<rmark;
return 0;
}
void find_page_range (int d, int k) {
int page;
int count, digit;
int page_ext;
int min_page = 0;
int max_page;
if ((d == 1) && (k == 0)) {
printf("min_page = 0, max_page = 0\n");
return;
}
count = 0;
page = 1;
while (count <= k) {
page_ext = page;
while (1) {
digit = page_ext%10;
page_ext = page_ext/10;
if(digit == d) {
count = count + 1;
}
if((count == k) && (min_page == 0)) {
min_page = page;
}
if(page_ext == 0) {
break;
}
}
page = page + 1;
}
max_page = page - 2;
printf("min_page = %d, max_page = %d\n", min_page, max_page);
return;
}
Here is my Python solution:
class Solution():
def occur(self, d, num):
s = [str(x) for x in list(range(1, num + 1))]
tmp = "".join(s)
return tmp.count(str(d))
def pageBounds(self, d, k):
if d ==1 and k == 0:
return (0,0)
lower = 0
upper = 40000
found = False
i = 1
while not found:
if self.occur(d, i) < k:
i += 1
elif self.occur(d, i) == k:
lower = i
found = True
for i in range(lower, 40000):
if self.occur(d, i) == k+1:
upper = i-1
break
return (lower, upper)
static unsigned int check_char_in_int(int niddle, int haystack)
{
char niddle_buff[20];
char haystack_buff[20];
memset(niddle_buff, sizeof(niddle_buff), 0);
memset(haystack_buff, sizeof(haystack_buff), 0);
snprintf(niddle_buff, sizeof(niddle_buff), "%d", niddle);
snprintf(haystack_buff, sizeof(haystack_buff), "%d", haystack);
if (strstr(haystack_buff, niddle_buff)) {
return 1;
}
return 0;
}
static void find_page_range(int digit, int occ)
{
int lower_bound = 1;
int upper_bound = 1;
int found_occ = 0;
int found_lower = 0;
while (1) {
if (found_lower == 0 && occ != 0) {
if (check_char_in_int(digit, lower_bound) == 1) {
found_lower = 1;
upper_bound = lower_bound+1;
found_occ++;
} else {
lower_bound++;
}
}
if (check_char_in_int(digit, upper_bound) == 1) {
found_occ++;
}
if (found_occ > occ) {
break;
} else {
upper_bound++;
}
}
printf("%d - %d\n", lower_bound, upper_bound-1);
}
Anybody care to take a stab at the time complexity for this solution I made?
public static void PrintPageCount(int d, int k)
{
StringBuilder stb = new StringBuilder();
Console.WriteLine("d = " + d + ". k = " + k);
int lower = -1;
int upper = -1;
int dCount = 0;
for (int i = 1; dCount <= k; i++)
{
dCount += BetterCountOfDigit(i, d);
if (lower < 0 && dCount == k)
{
lower = i;
upper = i;
} else if (dCount == k)
{
upper++;
}
if (dCount <= k)
Console.Write(i + " ");
}
Console.WriteLine();
Console.WriteLine("(" + lower + ", " + upper + ")");
}
public static int CountOfDigit(int number, int digit)
{
if (number == 0)
{
if (digit == 0)
return 1;
else
return 0;
}
return (number%10 == digit ? 1 : 0) + CountOfDigit(number/10, digit);
}
public class main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int d = sc.nextInt();
int k = sc.nextInt();
output(d, k);
}
public static void output(int d, int k) {
int lower, upper;
int cnt = 0;
int temp = 1;
if (k == 0) {
upper = d - 1;
lower = 1;
} else {
lower = d;
upper = 0;
while (cnt != k) {
upper++;
temp = upper;
while (temp > 0) {
if (temp % 10 == d) {
cnt++;
}
temp /= 10;
}
}
}
System.out.println(lower + "-" + upper + ", " + cnt);
}
}
I will just post a working code. You can test it out yourself. Pure C++.
The complexity,
countOccur -- O(logN) , N < 19*K
lowerBound -- O(log(19*K))
total: O(logN*log19K) = O ((log19K)^2)
#include <iostream>
#include <vector>
using namespace std;
//Count occurrence of digit d within number 1~n.
//It assumes n > 0 and d in [0,9]
int countOccur(int n, int d)
{
int sum = 0, l = 1, r = 0;
for (; n >= 1; n /= 10)
{
int q = n/10;
int m = n%10;
if (m > d)
{
q ++;
}
if (m == d)
{
sum += r + 1;
}
if (d == 0)
{
q --;
}
sum += q*l;
r = m*l + r;
l *= 10;
}
return sum;
}
//Find the lower bound of n, given digit d
//and occurrence k.
int lowerBound(int d, int k)
{
int l = 1, h = k*19;
while (l < h - 1)
{
int m = (l + h) / 2;
int c = countOccur(m, d);
if ( c < k)
{
l = m;
}else if (c >= k){
h = m;
}
}
return h;
}
int solve(int d, int k)
{
cout<<"["<<lowerBound(d, k)<<", "<<lowerBound(d, k+1)<<")"<<endl;
return 1;
}
int main()
{
cout<<countOccur(11,0)<<endl;
solve(0,5);
}
I will just post a working code. You can test it out yourself. Pure C++.
The complexity,
countOccur -- O(logN) , N < 19*K
lowerBound -- O(log(19*K))
total: O(logN*log19K) = O ((log19K)^2)
#include <iostream>
#include <vector>
using namespace std;
//Count occurrence of digit d within number 1~n.
//It assumes n > 0 and d in [0,9]
int countOccur(int n, int d)
{
int sum = 0, l = 1, r = 0;
for (; n >= 1; n /= 10)
{
int q = n/10;
int m = n%10;
if (m > d)
{
q ++;
}
if (m == d)
{
sum += r + 1;
}
if (d == 0)
{
q --;
}
sum += q*l;
r = m*l + r;
l *= 10;
}
return sum;
}
//Find the lower bound of n, given digit d
//and occurrence k.
int lowerBound(int d, int k)
{
int l = 1, h = k*19;
while (l < h - 1)
{
int m = (l + h) / 2;
int c = countOccur(m, d);
if ( c < k)
{
l = m;
}else if (c >= k){
h = m;
}
}
return h;
}
int solve(int d, int k)
{
cout<<"["<<lowerBound(d, k)<<", "<<lowerBound(d, k+1)<<")"<<endl;
return 1;
}
int main()
{
cout<<countOccur(11,0)<<endl;
solve(0,5);
}
import java.util.AbstractSet;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.TreeSet;
public class ComputeDigitOccurence {
static final int digit= 4;static final int occur=13;
public static void main(String[] args) {
TreeSet<Integer> list = new TreeSet<Integer>();
if(occur == 0){
int min=1,max = digit-1;
list.add(min);list.add(max);
}else{
list = occur(digit,occur,list);
}
System.out.println("["+list.first()+","+list.last()+"]");
}
private static TreeSet<Integer> occur(int next, int occurence,TreeSet<Integer> list) {
if(occurence==1){
return list;
} else {
if (!list.isEmpty()) {
Integer last = list.last();
char[] c = String.valueOf(last).toCharArray();
for (char ch : c) {
if (String.valueOf(ch).equals(String.valueOf(digit)))
occurence = occurence - 1;
}
}
list.add(Integer.valueOf(next));
list = occur(1 + next, occurence, list);
}
return list;
}
}
My solution would be like this..
public class Question3 {
/**
* @param args
*/
public static void main(String[] args) {
Map<String, Integer> result = getLowerAndUpperBound(4, 0);
System.out.println(result);
}
private static Map<String, Integer> getLowerAndUpperBound(int noToRepeat,
int occurence) {
Map<String, Integer> result = new HashMap<>();
if (occurence == 0) {
result.put("lower bound", 1);
result.put("upperbound bound", noToRepeat - 1);
} else {
boolean repeat = true;
int repeatition = 1;
int lowerBound = noToRepeat;
int upperbound = 0;
int i = lowerBound;
while (repeat) {
i++;
int count = doesCurrentNumberHasNumberToBeRepeated(i,
noToRepeat);
if (count>0) {
repeatition+=count;
}
if (repeatition > occurence) {
repeat = false;
upperbound = i;
}
}
result.put("lower bound", lowerBound);
result.put("upperbound bound", upperbound);
}
return result;
}
private static int doesCurrentNumberHasNumberToBeRepeated(int i,
int noToRepeat) {
int k = 0;
int j = 0;
if (i == noToRepeat) {
return 1;
} else if (i < noToRepeat) {
return 0;
} else if (i < 10) {
return 0;
} else {
int remainder = i % 10;
k = doesCurrentNumberHasNumberToBeRepeated(remainder, noToRepeat);
j = doesCurrentNumberHasNumberToBeRepeated(i / 10, noToRepeat);
}
return k+j;
}
}
#include <iostream>
#include <map>
using namespace std;
int GetNextNumberWithDigit(
const unsigned int Num,
const unsigned char Digit)
{
unsigned int Original = Num;
unsigned int Count = 0;
unsigned int LeftOver = 0;
unsigned int MultBy = 1;
//
// Find the least signficant occurence of Digit
//
while (Original != 0 &&
Original % 10 != Digit)
{
//
// This is the least significant number just before
// the appearance of Digit
//
LeftOver =
(((Original % 10)* MultBy)
+ LeftOver);
MultBy *= 10;
Original /= 10;
Count++;
}
if (Original == 0)
{
return (-1);
}
if (Count == 0)
{
//
// This is the case in which Digit is the first digit
// in the number Num
//
Original /= 10;
//
// if the digit after Digit is on less of it :
// say Digit is:5 and number is 45
// then the next number should be 50
//
if (Original % 10 == Digit - 1)
{
return ((Original / 10) * 10) + (Digit * 10);
}
//
// if the digit after Digit is equal to digit
// Num = 55 Digit = 5 then just return Num + 1
// However if Num is 99 and Digit = 9 we need to return
// 109
//
if (Original % 10 == Digit)
{
return (Num + 1 + (Digit * (Num + 1 % 10 == 0 ? 1 : 0)));
}
//
// this is the case in which Num = 35 and Digit = 5
// Just increase the number to 45
//
return (((Original + 1) * 10) + Digit);
}
//
// This will handle all cases in which the Digit is not
// the least significant digit of Num
//
unsigned int Temp = ++LeftOver;
unsigned int Count2 = 0;
while (Temp != 0)
{
//
// we multiply Original back by 10 to the power of Count2
//
Temp /= 10;
Count2++;
Original *= 10;
}
//
// if Count2 > Count we need to divide original by 10
// and in anycase add to original LeftOver.
// if Count2 > Count we also need to add Digit again:
// for example: 159,5 -> Original = 15 LeftOver++ = 10
// 15 * 10 + 10 = 160 we need to add the extra 5 at the end
//
return ((Original / (Count2 > Count ? 10 : 1)) + LeftOver + (Count2 > Count ? Digit : 0));
}
std::pair<int,int> GetBookPageRanges(unsigned int K, unsigned int D)
{
unsigned int Num = D;
for (int i = 1; i < K;)
{
Num = GetNextNumberWithDigit(Num, D);
unsigned Temp = Num;
//
// Count the number of occurences
// of D in Num and advance i by those
// occurances
//
while (Temp != 0)
{
if (Temp % 10 == D)
{
i++;
}
Temp /= 10;
}
}
unsigned int NextNum = GetNextNumberWithDigit(Num, D);
return make_pair(1, Num + (NextNum - Num - 1));
}
#include <iostream>
#include <map>
using namespace std;
int GetNextNumberWithDigit(
const unsigned int Num,
const unsigned char Digit)
{
unsigned int Original = Num;
unsigned int Count = 0;
unsigned int LeftOver = 0;
unsigned int MultBy = 1;
//
// Find the least signficant occurence of Digit
//
while (Original != 0 &&
Original % 10 != Digit)
{
//
// This is the least significant number just before
// the appearance of Digit
//
LeftOver =
(((Original % 10)* MultBy)
+ LeftOver);
MultBy *= 10;
Original /= 10;
Count++;
}
if (Original == 0)
{
return (-1);
}
if (Count == 0)
{
//
// This is the case in which Digit is the first digit
// in the number Num
//
Original /= 10;
//
// if the digit after Digit is on less of it :
// say Digit is:5 and number is 45
// then the next number should be 50
//
if (Original % 10 == Digit - 1)
{
return ((Original / 10) * 10) + (Digit * 10);
}
//
// if the digit after Digit is equal to digit
// Num = 55 Digit = 5 then just return Num + 1
// However if Num is 99 and Digit = 9 we need to return
// 109
//
if (Original % 10 == Digit)
{
return (Num + 1 + (Digit * (Num + 1 % 10 == 0 ? 1 : 0)));
}
//
// this is the case in which Num = 35 and Digit = 5
// Just increase the number to 45
//
return (((Original + 1) * 10) + Digit);
}
//
// This will handle all cases in which the Digit is not
// the least significant digit of Num
//
unsigned int Temp = ++LeftOver;
unsigned int Count2 = 0;
while (Temp != 0)
{
//
// we multiply Original back by 10 to the power of Count2
//
Temp /= 10;
Count2++;
Original *= 10;
}
//
// if Count2 > Count we need to divide original by 10
// and in anycase add to original LeftOver.
// if Count2 > Count we also need to add Digit again:
// for example: 159,5 -> Original = 15 LeftOver++ = 10
// 15 * 10 + 10 = 160 we need to add the extra 5 at the end
//
return ((Original / (Count2 > Count ? 10 : 1)) + LeftOver + (Count2 > Count ? Digit : 0));
}
std::pair<int,int> GetBookPageRanges(unsigned int K, unsigned int D)
{
unsigned int Num = D;
for (int i = 1; i < K;)
{
Num = GetNextNumberWithDigit(Num, D);
unsigned Temp = Num;
//
// Count the number of occurences
// of D in Num and advance i by those
// occurances
//
while (Temp != 0)
{
if (Temp % 10 == D)
{
i++;
}
Temp /= 10;
}
}
unsigned int NextNum = GetNextNumberWithDigit(Num, D);
return make_pair(1, Num + (NextNum - Num - 1));
}
#include <iostream>
#include <map>
using namespace std;
int GetNextNumberWithDigit(
const unsigned int Num,
const unsigned char Digit)
{
unsigned int Original = Num;
unsigned int Count = 0;
unsigned int LeftOver = 0;
unsigned int MultBy = 1;
//
// Find the least signficant occurence of Digit
//
while (Original != 0 &&
Original % 10 != Digit)
{
//
// This is the least significant number just before
// the appearance of Digit
//
LeftOver =
(((Original % 10)* MultBy)
+ LeftOver);
MultBy *= 10;
Original /= 10;
Count++;
}
if (Original == 0)
{
return (-1);
}
if (Count == 0)
{
//
// This is the case in which Digit is the first digit
// in the number Num
//
Original /= 10;
//
// if the digit after Digit is on less of it :
// say Digit is:5 and number is 45
// then the next number should be 50
//
if (Original % 10 == Digit - 1)
{
return ((Original / 10) * 10) + (Digit * 10);
}
//
// if the digit after Digit is equal to digit
// Num = 55 Digit = 5 then just return Num + 1
// However if Num is 99 and Digit = 9 we need to return
// 109
//
if (Original % 10 == Digit)
{
return (Num + 1 + (Digit * (Num + 1 % 10 == 0 ? 1 : 0)));
}
//
// this is the case in which Num = 35 and Digit = 5
// Just increase the number to 45
//
return (((Original + 1) * 10) + Digit);
}
//
// This will handle all cases in which the Digit is not
// the least significant digit of Num
//
unsigned int Temp = ++LeftOver;
unsigned int Count2 = 0;
while (Temp != 0)
{
//
// we multiply Original back by 10 to the power of Count2
//
Temp /= 10;
Count2++;
Original *= 10;
}
//
// if Count2 > Count we need to divide original by 10
// and in anycase add to original LeftOver.
// if Count2 > Count we also need to add Digit again:
// for example: 159,5 -> Original = 15 LeftOver++ = 10
// 15 * 10 + 10 = 160 we need to add the extra 5 at the end
//
return ((Original / (Count2 > Count ? 10 : 1)) + LeftOver + (Count2 > Count ? Digit : 0));
}
std::pair<int,int> GetBookPageRanges(unsigned int K, unsigned int D)
{
unsigned int Num = D;
for (int i = 1; i < K;)
{
Num = GetNextNumberWithDigit(Num, D);
unsigned Temp = Num;
//
// Count the number of occurences
// of D in Num and advance i by those
// occurances
//
while (Temp != 0)
{
if (Temp % 10 == D)
{
i++;
}
Temp /= 10;
}
}
unsigned int NextNum = GetNextNumberWithDigit(Num, D);
return make_pair(1, Num + (NextNum - Num - 1));
}
#include <iostream>
#include <map>
using namespace std;
int GetNextNumberWithDigit(
const unsigned int Num,
const unsigned char Digit)
{
unsigned int Original = Num;
unsigned int Count = 0;
unsigned int LeftOver = 0;
unsigned int MultBy = 1;
//
// Find the least signficant occurence of Digit
//
while (Original != 0 &&
Original % 10 != Digit)
{
//
// This is the least significant number just before
// the appearance of Digit
//
LeftOver =
(((Original % 10)* MultBy)
+ LeftOver);
MultBy *= 10;
Original /= 10;
Count++;
}
if (Original == 0)
{
return (-1);
}
if (Count == 0)
{
//
// This is the case in which Digit is the first digit
// in the number Num
//
Original /= 10;
//
// if the digit after Digit is on less of it :
// say Digit is:5 and number is 45
// then the next number should be 50
//
if (Original % 10 == Digit - 1)
{
return ((Original / 10) * 10) + (Digit * 10);
}
//
// if the digit after Digit is equal to digit
// Num = 55 Digit = 5 then just return Num + 1
// However if Num is 99 and Digit = 9 we need to return
// 109
//
if (Original % 10 == Digit)
{
return (Num + 1 + (Digit * (Num + 1 % 10 == 0 ? 1 : 0)));
}
//
// this is the case in which Num = 35 and Digit = 5
// Just increase the number to 45
//
return (((Original + 1) * 10) + Digit);
}
//
// This will handle all cases in which the Digit is not
// the least significant digit of Num
//
unsigned int Temp = ++LeftOver;
unsigned int Count2 = 0;
while (Temp != 0)
{
//
// we multiply Original back by 10 to the power of Count2
//
Temp /= 10;
Count2++;
Original *= 10;
}
//
// if Count2 > Count we need to divide original by 10
// and in anycase add to original LeftOver.
// if Count2 > Count we also need to add Digit again:
// for example: 159,5 -> Original = 15 LeftOver++ = 10
// 15 * 10 + 10 = 160 we need to add the extra 5 at the end
//
return ((Original / (Count2 > Count ? 10 : 1)) + LeftOver + (Count2 > Count ? Digit : 0));
}
std::pair<int,int> GetBookPageRanges(unsigned int K, unsigned int D)
{
unsigned int Num = D;
for (int i = 1; i < K;)
{
Num = GetNextNumberWithDigit(Num, D);
unsigned Temp = Num;
//
// Count the number of occurences
// of D in Num and advance i by those
// occurances
//
while (Temp != 0)
{
if (Temp % 10 == D)
{
i++;
}
Temp /= 10;
}
}
unsigned int NextNum = GetNextNumberWithDigit(Num, D);
return make_pair(1, Num + (NextNum - Num - 1));
}
#include <iostream>
#include <map>
using namespace std;
int GetNextNumberWithDigit(
const unsigned int Num,
const unsigned char Digit)
{
unsigned int Original = Num;
unsigned int Count = 0;
unsigned int LeftOver = 0;
unsigned int MultBy = 1;
//
// Find the least signficant occurence of Digit
//
while (Original != 0 &&
Original % 10 != Digit)
{
//
// This is the least significant number just before
// the appearance of Digit
//
LeftOver =
(((Original % 10)* MultBy)
+ LeftOver);
MultBy *= 10;
Original /= 10;
Count++;
}
if (Original == 0)
{
return (-1);
}
if (Count == 0)
{
//
// This is the case in which Digit is the first digit
// in the number Num
//
Original /= 10;
//
// if the digit after Digit is on less of it :
// say Digit is:5 and number is 45
// then the next number should be 50
//
if (Original % 10 == Digit - 1)
{
return ((Original / 10) * 10) + (Digit * 10);
}
//
// if the digit after Digit is equal to digit
// Num = 55 Digit = 5 then just return Num + 1
// However if Num is 99 and Digit = 9 we need to return
// 109
//
if (Original % 10 == Digit)
{
return (Num + 1 + (Digit * (Num + 1 % 10 == 0 ? 1 : 0)));
}
//
// this is the case in which Num = 35 and Digit = 5
// Just increase the number to 45
//
return (((Original + 1) * 10) + Digit);
}
//
// This will handle all cases in which the Digit is not
// the least significant digit of Num
//
unsigned int Temp = ++LeftOver;
unsigned int Count2 = 0;
while (Temp != 0)
{
//
// we multiply Original back by 10 to the power of Count2
//
Temp /= 10;
Count2++;
Original *= 10;
}
//
// if Count2 > Count we need to divide original by 10
// and in anycase add to original LeftOver.
// if Count2 > Count we also need to add Digit again:
// for example: 159,5 -> Original = 15 LeftOver++ = 10
// 15 * 10 + 10 = 160 we need to add the extra 5 at the end
//
return ((Original / (Count2 > Count ? 10 : 1)) + LeftOver + (Count2 > Count ? Digit : 0));
}
std::pair<int,int> GetBookPageRanges(unsigned int K, unsigned int D)
{
unsigned int Num = D;
for (int i = 1; i < K;)
{
Num = GetNextNumberWithDigit(Num, D);
unsigned Temp = Num;
//
// Count the number of occurences
// of D in Num and advance i by those
// occurances
//
while (Temp != 0)
{
if (Temp % 10 == D)
{
i++;
}
Temp /= 10;
}
}
unsigned int NextNum = GetNextNumberWithDigit(Num, D);
return make_pair(1, Num + (NextNum - Num - 1));
}
Solution:
- g233007 January 27, 20151. Get a rough range (say begin and end) of pages that for all page N with CheckOccurrence(N, d) == k, begin <=N<=end.
2. Use binary search in range [begin, end] to find the left and right boundary of result.
For CheckOccurrence (int n, int d):
1. Assume n = ABCD
2. Check occurrence of d in each digital place.
3. Assume current digital place is C
4. First check occurrence of d in place C from 0 - (AB-1)(9...). The count is AB. (E.g. n = 1234, C = 3 then this is to check from 0 - 1199 and the count is 11).
5. Then check occurrence of d in place C from AB(0..) - ABCD. If C > d then the count should be from ABK(0...) - ABK(9...) which is 10^position of D; if C == d then the count should be from ABK(0...) - ABKD which is D. (E.g. n = 1234, C = 3 then this is to check from 1200 - 1234, if d = 2 then count is 10; if d = 3 then count is 4; if d =5 then count = 0)Notice that if d is 0 then we don't need this part at all because we don't count 0C as count.
Time efficiency: CheckOccurrence method is constant number C since the upper boundary of number n is int.MaxValue, method of finding rough range and binary search are both O(LogN) where N is the upper boundary result so the overall time efficiency is O(LogN)
Space efficiency is O(1)