Google Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
2
of 2 vote

Solution:
1. 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)

- g233007 January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
        }
    }

- g233007 January 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@g233007 your method CheckOccurrence fails for finding occurrences of 3 in 33, it returns 8 while count should be 7:
3,13,23,30,31,32,33

- guilhebl March 26, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Source January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Source , could you please explain a little bit about the approach you have taken.

- root545 January 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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

- Source January 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Anon January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sry, 33 counts as two. I missed that.

- Anon January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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
	}

- Skor January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what is numPresent() is doing exactly ?

- Anonymous February 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Isaac January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- nickyang07 January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I would write a function checking that given N and d, if the number of occurrences of d on the string 1 to N is more than k or not. Then, I would do exponential search (which is similar to a binary search but I would use it as the upper bound of N is not given..)

- BS January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- ompranav January 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- ompranav January 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hey,
can you please explain the logic ?

- WeAreBack January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It looks like you're misunderstanding the question. Your solution would only work for k == 1. Since digits can only occur in the range 0-9, if digit d appears k times then k > 1 implies that N>d so arr[0] is not equivalent to d.

- Michael January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

/* 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);
	}
}

- Himanshu Jain January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Sumeet Singhal January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Michael January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sumeet Singhal January 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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}

- Bond January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it's saying the lowest bound that the highest page could be is 4 while the highest is 13. So it could be either 1 -4, or 4 -13. If {low, high} you'd get {4, 13}

- Dave January 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

let d = 1 and k = 3,

what is the output of that case ?

- eng.mohamed.CSD2014 January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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}?

- fgdsb January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous January 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);             
     }
}

- Sung January 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void numberOfPages(int d, int k) {
int i = d + 1;
int count = 1;
while (count < k + 1) {
int t = i;
while (t != 0) {
if (t % 10 == d)
++count;
t = t / 10;
}
i++;
}
if (k == 0)
d=0;
System.out.println(d + " " + (i - 2));
}

- pp2157 January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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()
    '''

- jilinxie1988@gmail.com January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

}

- Sumeet Singhal January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- Hank January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- snd January 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- Raymend January 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- Liad January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is an off by one error in the code it should be
upper_bound = lower_bound;
not
upper_bound = lower_bound+1;

- Liad January 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
        }

- dkoch74 February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Btw, all the print statements besides the one containing lower and upper are just visual niceties I added for debugging.

- dkoch74 February 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

- amutart February 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- fentoyal February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- fentoyal February 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]) {
		int d = 4;
		int k = 1;
		int n = 1;

		System.out.print("Book contains pages from ");
		for (int i = 0; i < k + 1; i++) {
			do {
				n++;
			} while (!String.valueOf(n).contains("4"));
			System.out.println(""+n);
		}
	}

- Anonymous February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}





}

- vinay February 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice recursion solution, but base case is wrong. Need return the upper bound.
input: digit =4, occur =1
output: should be [4,13] but yours is [4,5]

- biolxj12 February 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}
}

- Rahul Khanna February 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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));
}

- John Smith the Mormon. February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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));
}

- John Smith the Mormon. February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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));

}

- John Smith the Mormon. February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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));
}

- John Smith the Mormon. February 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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));
}

- John Smith the Mormon. February 18, 2015 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More