Amazon Interview Question
Software Development ManagersCountry: India
>>> candidates = range(0,13)
>>> for i in range(0,10):
print 'Occurences of %s' % (i)
reduce (str.__add__, map (lambda x: str(x), candidates)).count(str(i))
Occurences of 0
2
Occurences of 1
5
Occurences of 2
2
Occurences of 3
1
Occurences of 4
1
Occurences of 5
1
Occurences of 6
1
Occurences of 7
1
Occurences of 8
1
Occurences of 9
1
Code:
public static void main(String[] args) {
int N = 552;
digitOccurrences(N);
}
public static void digitOccurrences(int N)
{
int[] count = new int[10];
count[0] = 1;
for (int i = 1; i <= N; i++)
{
//# of digits in i
int numDigits = 1;
while(i/(int)Math.pow(10, numDigits) > 0)
{
numDigits++;
}
//evaluate i and add all digits to counter array
int temp = i;
while(numDigits > 0)
{
int k = temp / (int)Math.pow(10, numDigits-1);
count[k]++;
temp -= k * (int)Math.pow(10, numDigits-1);
numDigits--;
}
}
//print occurrences
for(int j = 0; j < 10; j++)
{
System.out.println(count[j]);
}
}
Output:
106
216
216
215
215
161
105
105
105
105
main()
{
int a[10], range, rem=0,quot =0, i;
printf("\n What range you want ? : ");
scanf("%d",&range);
bzero(a,10*sizeof(int));
a[0] =1;
while(range)
{
if(range < 10)
{
rem = range%10;
a[rem] +=1;
range--;
}
else
{
quot = range/10;
a[quot] +=1;
rem = range%10;
a[rem] +=1;
range--;
}
}
printf("\n");
for(i=0; i < 10; i++)
printf("Num of %ds %d\n", i,a[i]);
}
My approach would be to count appearances of each digit according to the number of digits in the range instead of the range itself, in other words I'll count the number of appearances of each digit 0-9 as the lsb, the 2nd digit from the lsb, the 3rd digit from the lsb and so forth. This would result in an O(logn) algorithm.
Given n and some digit 0<=d<=9, how do we count the number of times the digit d appears in n? First, we'll need to divide it to two cases: d=0 and 1<=d<=9.
1. 1<=d<=9. We want to count how many times d appears in the range 0...n as the i-th digit (from the lsb). Let k = 10^(i+1). How many times does d appear as the i-th digit in the range 0...k? It's easy to see that it appears exactly k/10 times (For example: How many times does the digit 1 appear as the second digit in the range 0...100? It appears exactly 10 times for the numbers 10,11,12,...,19). The same applies to the range k+1,...,2k and so on.
Hence, (n/k)*(k/10) is the number of appearances (of d as the i-th digit) in the range 0...Integer(n/k)*k.
We're not done yet though because there may be a remainder from the division of n by k which we didn't handle. Let us look at the remainder 0 <= n % k < k. If (n % k) / (k/10) is greater than d that means the remainder (n % k) > d*(k/10) which means that the digit d appears as the i-th digit in the remainder k/10 times as well (For example: for the number n=120 and d=1, the remainder n % 100 = 20. Then, 20/10 = 2 > 1 which means that there are 10 more appearances of 1 as the i-th digit in the remainder: 10,11,12,...,19).
If (n % k)/(k/10)<d then there are no appearances of d as the i-th digit in the remainder.
All that's left is to handle the case where (n % k)/(k/10)==d. In this case, the number of appearances would be (n % k) % (k/10) + 1 (1 is added because the count starts from 0). For example: n=115 and d=1: (115 % 100) / (100/10) == 1 and (115 % 100) % 10 +1 = 5+1=6 which accounts for the appearance of d=1 as the 2nd digit in the numbers 110 (10 in the remainder), 111 (11), ... , 115 (15).
These observations allow us to calculate the number of appearances of 1<=d<=9 as the i-th digit in the range 0...n with O(1) run-time complexity.
2. d=0. This case is slightly trickier because 0 cannot appear as msb (We cannot count 10 appearances of 0 as the 2nd digit in the range 10). Still, we'll try and solve it with a similar but slightly modified approach. Let us look again at (n/k) - k is the same as in (1), the number of appearances of 0 as the i-th digit in the range 0...k-1 is 0 because all the numbers in that range have i digits or less. On the other hand, in the range k...2k-1 it appears k/10 times (For instance, d=0 appears 0 times as the 2nd digit in the range 0...99 but it appears appears 10 times in as the 2nd digit in the range 100...199 and another 10 times in the range 200...299). So the number of appearances of d=0 as the i-th digit in the range 0...Integer(n/k)*k is Math.max((n/k)-1,1)*(k/10).
As before, we're not quite done yet because n/k might have a remainder. But the remainder n % k has at most i digits, when should we count d=0 as msb considering that remainder? Using the same idea as in (1), we'll count it relative to k/10. If n % k >= k/10 that means we need to count k/10 appearances in the remainder (For instance: n=110, n % 100 = 10 and 10 >= 100/10 which means we have 10 appearances in the remainder: 100(00), 101(01),...,109(09)). If n % k < k/10 then the number of appearances is (n % (k/10)) + 1.
The resulting (slightly confusing) code is:
private static int countForDigit(int n, int d){
if ((n<0) || (d<0) || (d>9)){return 0;}
if ((n==0) && (d==0)){return 1;}
int res = 0;
for (int k=10;(k==10) && ((n/k)>0) || (n/(k/10)>0);k*=10){
if (k==10){res+=(n/k) + ((n % k >= d) ? 1 : 0);}
else {
if (d>0){
res+=(n/k)*(k/10) + ((((n % k)/(k/10))) > d ? k/10 : (((n % k)/(k/10) == d) ? ((n % k) % (k/10))+1 : 0));
}
else{
res+=(Math.max((n/k)-1, 0))*(k/10) + Math.min((n/k),1)*((n % k >= (k/10)) ? (k/10) : (n % (k/10)) + 1);
}
}
}
return res;
}
public static int[] getAllDigitsCount(int n){
if (n<0){return null;}
int[] count = new int[10];
for (int d=0;d<count.length;d++){count[d]=countForDigit(n,d);}
return count;
}
Complexity: 10*O(logn) = O(logn) run-time complexity.
#include<stdio.h>
#include<conio.h>
void main(){
int n,i,temp,rem;
int arr[]={0,0,0,0,0,0,0,0,0,0};
printf("Enter the number: ");
scanf("%d",&n);
for(i=0;i<=n;i++){
temp=i;
if(temp!=0){
while(temp!=0){
rem=temp%10;
arr[rem]+=1;
temp=temp/10;
}
}
else
arr[0]+=1;
}
for(i=0;i<10;i++)
printf("\nNumber of %ds is: %d",i,arr[i]);
getch();
}
// Find number of occurrences of 0 to 9 upto 1 to 100
public class FindNumOfOccurrences {
public static void main(String[] args) {
findCount(9);
}
public static void findCount(int num)
{
int count=0;
for(int i=0;i<100;i++)
{
int a=i/10;
int b=i%10;
if(a==num)
count++;
if(b==num)
count++;
}
System.out.println("Number of "+ num +"'s= "+count);
}
}
Here is my solutions.
public static void main(String[] args){
int num = 56705678;
findDigitalOccurences(num);
}
public static void findDigitalOccurences(int n) {
int[] digitals = new int[10];
Arrays.fill(digitals, 0); /*may skip since the default value of array element are all 0; */
int num = n;
while (num / 10 >= 1) {
int a = num % 10;
num = num / 10;
digitals[a]++;
}
digitals[num]++;
for (int k = 0; k < 10; k++) {
System.out.println(digitals[k]);
}
}
If I understood the problem statement correctly, one wants to find the number of occurrences of each digit in an integer. For example, n=9838556. has 1x "9", 2x "8", 1x "3", 2x "5", and 1x "6". The pseudo code can be a while loop that terminates as follows:
counters [10] ; is an array of counters initially set to 0 where each element represents a digit between 0 and 9. In this example at the end of the program counters[9]=1, counters[8]=2, .....
n=9838556 ;as an example
While (true) {
if (n==0) break ;break out of the while loop while all digits counted
counters[n mod 10]++ ;increment counter for the digit
n=(n-(n mod 10))/10
}
; The above algorithm is super fast as the number of loops depend on the number of digits in an integer. For example, an integer that has 20 digits, will be processed by looping 20 times.
what we can do in this question is initialize an array like this:-
- reyanshjain91 January 27, 2014arr={1,0,0,0,0,0,0,0,0,0}
this array represent the occurrence of a digit as
arr[0] for 0 occurrence, arr[1] for 1 occurrence....
Now,
if(n!=0)
{
for(int i=1;i<n; i++) //this will increase the series from 1 to n
{
while(i!=0)
{
int rem= i%10;
arr[rem]= arr[rem]+1;
//this increase the value of rem digit by 1 in arr array
//for ex:-
//if the value of i is 456 then
//rem will be 456%10 i.e 6 and now arr[rem] will be //arr[6] and it will increased by 1.
i=i/10;
}
}
}
for(int i=0; i<=9; i++)
cout<<arr[i]; //this will print the occurrence of all the digit