## Amazon Interview Question for SDE-2s

Country: India

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

int countDigits(int num) {

int rem = num;
int count = 0;

while(rem > 0){

rem = rem / 10 ;
count ++;
}

return count ;

}

void digitsCountFrom(int from, int to)
{
int *digitsCount = (int *) malloc( to *sizeof(int)) ;
int i,k ;

for(i=from, k=0 ; i<=to; i++, k++)
{
digitsCount[k] = countDigits(i);
printf("digitsCount[%d] : %d\n",i,digitsCount[k] );
}

free(digitsCount);
digitsCount = NULL ;
}

int main(int argc, const char * argv[])
{
digitsCountFrom(1,100) ;

return 0;
}

Comment hidden because of low score. Click to expand.
0

#include<iostream>
using namespace std;

void count(int *a,int n){
int i;
for(i=0;i<=n;i++){
int num=i;
while(num >0){
a[num%10]++;
num=num/10;

}

}
}

int main(){

int a[10]={0},n=100;
count(a,n);

int i;

for(i=0;i<10;i++){
cout<<a[i]<<"\t";
}

}

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

I guess i was not clear. Counting digit means total number of occurrences of digits 0,,1,2,3,4,5..9 in that range.

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

This works for 2 digit. Not sure how to make it dynamic for all.

``````public static void countNumberJumbel(int from, int to){
if(from > to){
System.out.println("From value cannot be more than To Value");
}else{
for(int i=from; i<to; i++){
int unit = i%10;
int tens = i/10;
numberOfDigit[unit]++;
numberOfDigit[tens]++;
}

for(int itr=0; itr< numberOfDigit.length; itr++){
System.out.println("numberOfDigit["+itr+"] = "+numberOfDigit[itr]);
}
}
}``````

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

a very naive implementation goes like to iterate from 0 to N.
Parse each digit and add digits to digit array.

``````#include <iostream>
#include "stdlib.h"
using namespace std;

void updateDigits (int *digits, int num)
{
if (num == 0)
{
digits[0] += 1;
return;
}
int k = 0;
while (num > 0)
{
k = num%10;
digits[k] += 1;
num = num/10;
}
}

void countDigits (int num)
{
int j = 0;
int digits[10] = {0};
for (j = 0; j <= num; j++)
{
updateDigits (digits, j);
}
for (j = 0; j <= 9; j++)
{
cout << "digits[" << j <<"]" << digits[j] << endl;
}
}
int main(int argc, char* argv[]) {
countDigits (299);
return 0;
}

Output:
digits[0]50
digits[1]160
digits[2]160
digits[3]60
digits[4]60
digits[5]60
digits[6]60
digits[7]60
digits[8]60
digits[9]60``````

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

geekyjumps.blogspot.in/2014/01/given-number-n-now-find-number-of.html

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

The solution is simpler than iterating from 0 to n and counting the digits:
This solution is O(log n) instead of O(n).

``````void countDigits(int n)
{
int digits[10], j, multiplier = 1, m=n;
for (j=0; j< 10; j++)
digits[j] = 0;

if (n == 0) // Edge case: n is 0
digits[0] = 1;

while (n>0)
{
int current = n % 10;
for (j=0;j<10;j++)
digits[j] += (n /10) * multiplier + (j < current)*multiplier;
digits[current] += (m % multiplier)+1;
if (multiplier > 1)
digits[0] -= multiplier;
n /= 10;
multiplier *= 10;
}

for (j=0; j<10; j++)
printf("digits[%d]=%d\n",j,digits[j]);
}``````

Comment hidden because of low score. Click to expand.
0

Output for your logic giving some wrong results, only for digit[0]
n=199,
output
digits[0]=30

n=209
output
digits[0]=31

clearly, there should be digits[0] = 41 for n=209
anyways, i didn't go through your algo.

Comment hidden because of low score. Click to expand.
0

Thanks for point out the error. I have updated the algorithm.

The idea is simple. Count how many times does every number appear in every position using the most significant digits and using the least significant digits and itself.
The 0 should be corrected as it could not be the most significant digit.

For example:
n = 209
for the units:
0 to 9 will appear 20 times (from 00 to 19 inclusive) + 1 more time for 20
for the tens:
0 to 9 will appear 2 times * 10 (from 0 to 1 inclusive) + (9+1) more times for 0
for the hundreds:
0 to 9 will appear 0 times * 100 (from 0 to 0) + 1 more time *100 for 0 and 1 - 100 for 0 + (9+1) times for 2

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

How will we modify this code if we want to get the number of digits within a range?
Here the range is assumed to be 0-n.

Comment hidden because of low score. Click to expand.
0

If you want from k to n , then count from 0 to n and remove the 0 to k part from the array of buckets.
If you need to take into account negative numbers, then add from -m to 0 (doing 0 to m).

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

``````void getcount(int n)
{
int digits[10];
int i,pow;
for(i=0;i<10;i++)
digits[i]=0;
digits[0]=1;
for(i=1;i<=n;i++)
{
pow=i;
while(i>0)
{
digits[i%10] += 1;
i=i/10;
}
i=pow;
}
for(i=0;i<10;i++)
printf("count %d is %d\n",i,digits[i]);``````

}

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

import java.util.HashMap;
import java.util.Map;

public class CountDigits {

public static void main(String args[]) {
countDigits(1, 200);

}

private static void countDigits(int i, int j) {
HashMap<String, Integer> numCnt = new HashMap<>();
//map<digit,count>
for (int n = i; n <= j; n++) {
String num = String.valueOf(n);
for (int k = 0; k < num.length(); k++) {
if (numCnt.containsKey(String.valueOf(num.charAt(k)))){
numCnt.put(String.valueOf(num.charAt(k)), numCnt.get(String.valueOf(num.charAt(k))) + 1);
} else {
numCnt.put(String.valueOf(num.charAt(k)), 1);
}
}
}
for (Map.Entry<String, Integer> ele : numCnt.entrySet()) {
System.out.println("Number" + ele.getKey() + ",Count:"
+ ele.getValue());
}
}

}

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.

### 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.