Amazon Interview Question
Software Engineer / DevelopersTeam: payments
Country: India
Sorry the sample input output did not come properly.
please find it here.
drive.google.com/file/d/0B2MCIfvwfpg2WW1XdjgwS282Q1U
This problem can be solved very efficiently with recursion. The algorithm below runs in O(log(n)).
def getNumberOfOcurrencesOfDigits(int N) {
def result = [0:0, 1:0, 2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0, 9:0]
def addToAll = getNumberOfOcurrencesOfDigits(N, result)
(0..9).each {
result[it] += addToAll
}
return result
}
def getNumberOfOcurrencesOfDigits(int N, result) {
int Nby10 = N / 10
int Nmod10 = N % 10
(1..Nmod10).each {
result[it]++
}
if(Nby10 > 0) {
return Nby10 + getNumberOfOcurrencesOfDigits(Nby10, result)
} else {
return 0
}
}
Thanks for sharing!
nice but wrong... at least you're on the right track
one remaining problem:
N = 12345
In the first iteration your are right that every digit has to appear 1234 times in the right most place.
In the second iteration N = 1234, now every digit in the right most place has to appear 123 times according to your logic, but as there is a degree of freedom it has to apper 123 times * 10
In the next step N = 123, every digit has to apper 12 times but is supported by two degrees of freedom -> 12*100
#include <stdio.h>
#include <string.h>
main()
{
int num = 0;
printf(" ENter a page number");
scanf("%d" , &num);
int pos =1;
int r;
int count[10], c,i, tpos;
for(c = 0 ; c < 10 ; c++)
count[c] =0;
while(num > 0)
{
r = num%10;
num = num/10;
for(i = 0; i <10 ; i++)
{
tpos = pos/10;
while(tpos > 0)
{
count[i] +=r* tpos;
tpos= tpos/10;
}
if(i <= r)
count[i] += 1;
}
pos = pos*10;
}
count[0]-=2;
for(i = 0; i < 10 ; i ++)
{
printf("\n number %d , count % d", i , count[i]);
}
}
Can be solved depending on the number of digits.
First lets identify the pattern of frequency of usage of each digit
0-9 : 1
10-99 : 10+10
100-999 : 100+100+100
let N be the input number and A be an array to store frequency of digits
Scan the number from left to right and extract each digit out of it. Let the digit be k and position be j e.g. N = 4375 for k = 4, j = 3
For each digit in N
for i = 0 to k-1
for x = 0 to 9
A[x]+= 10^(j-1)
A[k] += N%10^j
initialize an array of int[10] from 0 .. 9
for each i in N keep getting reminder of i / 10 and increment array for each value found.
public static void getNumberOfOcurrencesOfDigits(int n) {
int[] sums = new int[10];
for (int i = 0; i < 10; i++) {
sums[i] = 0;
}
sums[0]++;
for (int i = 1; i <= n; i++) {
int rem = i % 10;
int div = i / 10;
sums[rem]++;
while (div > 0) {
rem = div % 10;
div = div / 10;
sums[rem]++;
}
}
for (int i = 0; i < sums.length; i++) {
System.out.println(i + " = " + sums[i]);
}
}
Here is a simple and pretty straightforward solution in Java:
long time = System.currentTimeMillis();
int number = 138493;
int[] result = {0,0,0,0,0,0,0,0,0,0}; //array of size 10 for each digit
int previousDivisor = 1;
int divisor = 10;
int allIncrement = 0;
while(true){
int dividedValue = number / divisor;
if(dividedValue > 0){
allIncrement += dividedValue;
}
int rest = (number % divisor) / previousDivisor;
for(int i=1;i<=rest;i++){
result[i]++;
}
if(dividedValue == 0){
break;
}
previousDivisor *= 10;
divisor *= 10;
}
System.out.println("Time: "+ (System.currentTimeMillis() - time));
for(int i=0;i<result.length;i++){
result[i]+=allIncrement;
System.out.println("Number of occurrences of "+i+" is equal to: "+result[i]);
}
This seems to work, complexity is O(logn) where n = input number or maybe in other words O(N) for N = (""+number).lenght()
public int[] countOccur(int n){
int[] occurence = new int[10];
int count = getshiftCount(n, occurence, 0, 1);
for (int i = 0; i < 10; i++){
occurence[i] += count;
}
if (n > 10){
occurence[0]--;
}
return occurence;
}
private int getshiftCount(int n, int[] occurence, int last, int power) {
int grade = n / 10;
int remainder = n % 10;
for (int i = 0; i < remainder; i++){
if (grade == 0 && i == 0){
continue;
}
occurence[i] += power;
}
occurence[remainder] += last + 1;
if (grade > 0){
return grade + getshiftCount(grade, occurence, remainder * power + last, power * 10);
} else {
return 0;
}
}
public static void main(String[] args) {
int s[] = new int[10];
int number = 999; // 189 +3=192 for 1000
doSum(s, number, number, 0, 0);
printSums(s);
}
private static void doSum(int[] s, int orig, int num, int low, int pow) {
int n = num / 10;
int r = num % 10;
if (n == 0 && r == 0)
return;
for (int i = 0; i < s.length; i++) { // lowest digit
s[i] = s[i] + n * (int) Math.pow(10, pow);
}
for (int i = 0; i <= r; i++) {
if ((pow == 0 || i < r)) {
s[i] = s[i] + 1 * (int) Math.pow(10, pow);
} else {
s[i] = s[i] + low + 1;
}
}
s[0] = s[0] - (int) Math.pow(10, pow);
doSum(s, orig, n, orig % (int) Math.pow(10, pow + 1), pow + 1);
}
private static void printSums(int[] sums) {
for (int i = 0; i < sums.length; i++) {
System.out.println("Digit " + i + "=" + sums[i]);
}
}
Best Explantation for this problem
- user124 February 08, 2014stackoverflow.com/questions/20945790/count-the-number-of-ks-between-0-and-n