## Amazon Interview Question for Software Developers

Country: United States

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

My answer for n < 10^18. Complexity is O(numbersDigits(n))

``````def count2(n):
total2 = [0 for i in range(0, MAX_DIGIT)]

# total 2s from 0 to 9
total2[1] = 1

# continue calculate 2s from 0 to 99, 0 to 999, etc...
for i in range(2, MAX_DIGIT):
total2[i] = total2[i - 1] * 10 + 10**(i - 1)

# example: 123 = 1 * total2[2] + 2 * total2[1] + 23 + 3 * total2[0] + 10^0
for i in range(len(n)):
# calculate number of 2 exists
value = int(n[i])
digits = len(n) - i - 1

# if this digits is 2, increase answer by all remains value
if value == 2:
answer += int("0" + n[i + 1:len(n)]) + 1

# if this digits is larger than 2, increase answer by 10**digits
if value > 2:

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

``````//ZoomBA
def count_2( n ){
sum( [2:n+1] ) ->{
sum ( str(\$.o).value ) ->{ \$.o == '2' ? 1 : 0 }
}
}``````

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

public int numberOfKs(int k,int n){

int count=0;

for(int i=k;i<=n;i++){

if(i==k){
count++;
}

else{
int tmpNum=i;

while(tmpNum!=0){

int rem=tmpNum%10;
tmpNum=tmpNum/10;

if(rem==k){
count++;
}

}

}

}

return count;

}

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

``````public class TwoCounter {
private int n;

public TwoCounter(int n) {
this.n = n;

}

public void numberOfCount() {
int length = 0;
String len = "";
for (int i = 0; i < n + 1; i++) {
len += i;

}
System.out.println(len);
char[] newRey = len.toCharArray();

for (char ch : newRey) {
if (ch == '2') {
length += 1;
}

}
System.out.println(length);
}

}``````

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

``````public class TwoCounter {
private int n;

public TwoCounter(int n) {
this.n = n;

}

public void numberOfCount() {
int length = 0;
String len = "";
for (int i = 0; i < n + 1; i++) {
len += i;

}
System.out.println(len);
char[] newRey = len.toCharArray();

for (char ch : newRey) {
if (ch == '2') {
length += 1;
}

}
System.out.println(length);
}

}``````

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

``````Lets put F(n) - number of 2s... Lets call F[a1,a2) - number of 2s between a1 and a2-1 and F[a1,a2] - between a1 and a2. So, F(n) == F[0,n] == F[0,n+1).
First, lets see how many 2s are in [0, 10^k].
F(10)= 1;
F(100) 	= F[0,10)+F[10,20)+F[20,30)+...F[90,100) = 9*F(10) + (10+F(10)) =20
F(1000) 	= F(100)+F[100,200)+F[200,300)+...F[900,1000) = 9*F(100) + (100+F(100)) = 300
F(10^(k+1)) = 10^k + 10*F(10^k) = 10^k +10*(10^(k-1) + 10*(...)) = (k+1)*10^k;
So, F(10^k) = k*10^(k-1).
Now, lets present number n as [a0,a1,a2,...,ak] when n = a0+a1*10+...+ak*10^k.
Then,
if(ak==0)
F([a0,a1,a2,...,0]) = 	F([a0,a1,a2,...,a(k-1)])
elseif(ak==1)
F([a0,a1,a2,...,1]) = 	F([a0,a1,a2,...,a(k-1)]) + 1*F(10^k)
elseif(ak==2)
F([a0,a1,a2,...,2]) = 	F([a0,a1,a2,...,a(k-1)]) + 1+[a0,a1,a2,...,a(k-1)] + 2*F(10^k)
else
F([a0,a1,a2,...,ak]) = 	F([a0,a1,a2,...,a(k-1)]) + 10^k + ak*F(10^k)

so...
ULONG Count2(ULONG n) {
ULONG nRet = 0;
ULONG n10deg = 1;//10^(nK-1)
ULONG nK = 0;
ULONG n1 = 0; //a mod 10^nK
while (n) {
ULONG a = n % 10;
switch (a) {
case 0: break;
case 1: nRet += nK*n10deg; break;
case 2: nRet += 1 + n1 + 2 * nK*n10deg; break;
default: nRet += n10deg + a*nK*n10deg;
}
if (nK)
n10deg *= 10;
++nK;
n1 = n1 * 10 + a;
n /= 10;
}
return nRet;
}``````

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

Thinking it's O(nm) where n=number of numbers and m is the average # of digits of the numbers

``````#include <stdio.h>

int twosInRange(int max);
int twosInNum(int n);

int twosInRange(int max) {
int counter = 0;
for (int i=0; i<=max; ++i) {
counter += twosInNum(i);
}
return counter;
}

int twosInNum(int n) {
int counter = 0;
while (n != 0) {
if ( (n-2) % 10 == 0 ) {
counter += 1;
}
n /= 10;
}
return counter;
}

int main()
{
int n = 29;
int ans = twosInRange(n);
printf("Q: %d\n - Ans: %d\n", n, ans);

return 0;
}``````

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

I think it's O(nm) where n= number of numbers, m= avg # of digits in the numbers.

``````#include <stdio.h>

int twosInRange(int max);
int twosInNum(int n);

int twosInRange(int max) {
int counter = 0;
for (int i=0; i<=max; ++i) {
counter += twosInNum(i);
}
return counter;
}

int twosInNum(int n) {
int counter = 0;
while (n != 0) {
if ( (n-2) % 10 == 0 ) {
counter += 1;
}
n /= 10;
}
return counter;
}

int main()
{
int n = 29;
int ans = twosInRange(n);
printf("Q: %d\n - Ans: %d\n", n, ans);

return 0;
}``````

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

I think its O(nm) where n= # of numbers, m=avg # of digits in each number

``````#include <stdio.h>

int twosInRange(int max);
int twosInNum(int n);

int twosInRange(int max) {
int counter = 0;
for (int i=0; i<=max; ++i) {
counter += twosInNum(i);
}
return counter;
}

int twosInNum(int n) {
int counter = 0;
while (n != 0) {
if ( (n-2) % 10 == 0 ) {
counter += 1;
}
n /= 10;
}
return counter;
}

int main()
{
int n = 29;
int ans = twosInRange(n);
printf("Q: %d\n - Ans: %d\n", n, ans);

return 0;
}``````

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

I'm going to assume that the numbers are in base 10 and that the digits are counted independently - i.e. 22 counts as two 2's.

This solution iteratively takes the most significant digits, converts them into their own integer, and adds that to the total. Each of these numbers represent the number of 2's in the following decimal place. For example, in the number 540, the number 54 is the number of 2's in the ones place. We'll also add 1 depending on whether the digit in the following decimal place is greater than or equal to 2.

``````def count2s(n):
n = '0' + str(n)
c = len(n)
total = 0
for i in range(1, c):
total += int(n[0:i]) + (int(n[i])>=2)

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

``````ulong numberOfKs(ulong n, byte K)
{
if (K > 9) throw new ArgumentOutOfRangeException("K");
ulong sum = 0, pow = 1, i = n;
while (i > 0)
{
ulong fullTens = i / 10;
ulong reminder = i % 10;
if (reminder > K)
fullTens += 1;
sum += fullTens * pow;
if (reminder == K)
sum += n % pow;
i = i / 10;
pow = pow * 10;
}
return sum;
}``````

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

``````public static int counting2s(int num)                        //Time Complexity:
{

int cnt = 0;
for (int i = 0; i <= num; i++)
{

int currnum = i;
while (currnum!= 0)
{
int digit = currnum % 10;
if (digit == 2)
cnt++;

currnum = currnum / 10;
}

}

return cnt;
}``````

What do you think?

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

``````public static int counting2s(int num)
{

int cnt = 0;
for (int i = 0; i <= num; i++)
{

int currnum = i;
while (currnum!= 0)
{
int digit = currnum % 10;
if (digit == 2)
cnt++;

currnum = currnum / 10;
}

}

return cnt;
}``````

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

public class Count2InNumber {

public static String removeString(String s, String[] arr){

for(int j=0;j<arr.length;j++){
for(int i=0;i<=arr.length-1;i++){
if(s.indexOf(arr[i])!=-1){
s = s.replaceAll(arr[i], "");

System.out.println("a[i]: "+arr[i]);
System.out.println("String : "+s);
}
}
}
return s;
}

public static void main(String[] args){
Scanner scan = new Scanner(System.in);
System.out.println("Enter the nth number");
int n = scan.nextInt();
int count = 0;

for(int i = 2;i<=n;i++){

String s = new String(new Integer(i).toString());
char[] arr = new char[s.length()];
arr= s.toCharArray();

for(int j = 0; j<arr.length;j++){
if(arr[j]=='2'){
count++;
}

}

}

System.out.println("Nunber of 2's from 0..."+n+"number "+ count);

}//end of main

}//end of class

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

``````public class Numof2s {

static int count =0;

public static void main(String[] args) {

int n =32;
int i;
int num;

for(i=1;i<=n;i++)
{
num =i;
while(num!=0)
{
if(num%10==2)
count++;
num=num/10;
}
}

System.out.println(count);

}

}``````

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

``````public class NumOfTwos {

public static void main(String[] args) {

int n=40;
int no=1;
int rem=0;
int count=0;
for(int i=1;i<=n;i++)
{
no=i;

while(no>0)
{
rem=no%10;
if(rem==2)
{
count++;
System.out.println(no);
}
no=no/10;

}

}
System.out.println(count);

}

}``````

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

``````from collections import Counter

def count_2s(n):
twos = 0
for i in xrange(n):
counter = Counter(str(i))
twos += counter.get('2', 0)
return twos``````

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

``from collections import Counter``

``def count_2s(n):``

``twos = 0``

``for i in xrange(n):``

``counter = Counter(str(i))``

``twos += counter.get('2', 0)``

``return twos``

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

``````from collections import Counter

def count_2s(n):
twos = 0
for i in xrange(n):
counter = Counter(str(i))
twos += counter.get('2', 0)
return twos``````

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

from collections import Counter

def count_2s(n):
twos = 0
for i in xrange(n):
counter = Counter(str(i))
twos += counter.get('2', 0)
return twos

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

``````from collections import Counter

def count_2s(n):
twos = 0
for i in xrange(n):
counter = Counter(str(i))
twos += counter.get('2', 0)
return twos``````

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

``````from collections import Counter
def count_2s(n):
twos = 0
for i in xrange(n):
counter = Counter(str(i))
twos += counter.get('2', 0)
return twos``````

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

static void Main(string[] args)
{
int n = 10;//use any value
int c=0;
while (n != 0)
{
int n1 = n;
do
{
int n2 = n1 % 10;
if (n2 == 2)
{
c++;
}
n1 = n1 / 10;

} while (n1 != 0);
n--;
}

Console.WriteLine(c);

}

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

``````static void Main(string[] args)
{
int n = 10;
int c=0;
while (n != 0)
{
int n1 = n;
do
{
int n2 = n1 % 10;
if (n2 == 2)
{
c++;
}
n1 = n1 / 10;

} while (n1 != 0);
n--;
}

Console.WriteLine(c);

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

dddd

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

``dddd``

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

Usage: getCountsfast(12345,'2');

``````unsigned int getCountsfast(unsigned int uiNum, char ch)
{
if((uiNum>=0) && (uiNum<=9)){
// single digit number
if(uiNum+'0' >= ch){
// If the number is >= required char, return 1.
return 1;
}else {
// Else, return 0.
return 0;
}
}else {
// 2 or more more digits in number
// 499 = 4(20)+100+20 = 200
//counts(ba,x) = b*counts(9,x)+ ((b>x)? 10:0) + ((b==x)? rem:0)+ counts(a,x)
//counts(cba,x) = c*counts(99,x) + ((c>x)?>100:0) + ((c==x)? rem:0) + counts(ba,x);

unsigned int uiNumTmp = uiNum/10;
unsigned int uiPow = 1;
while(uiNumTmp > 0){
uiPow = uiPow*10;
uiNumTmp = uiNumTmp/10;
}
unsigned int uiMsd = uiNum / uiPow;
unsigned int uiRem = uiNum - (uiMsd*uiPow);
unsigned int uiFullCounts = uiMsd*getCountsfast(uiPow-1,ch);
unsigned int uiMidCounts = ((uiMsd+'0'>ch)?uiPow:0) + ((uiMsd+'0'==ch)?(uiRem+1):0);
unsigned int uiRemCounts = getCountsfast(uiRem,ch);
return uiFullCounts + uiMidCounts+ uiRemCounts;
}
}``````

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

public static void numberOfTwos(int n) throws Exception
{
int twosCount = 0;
int factor = 0;

if( n < 0 )
{
throw new Exception();
}

while( n != 0 )
{
int lsd = n % 10;

twosCount += lsd * factor;

if( lsd >= 2 )
{
twosCount++;
}

n /= 10;
factor = factor * 10 + 1;
}

System.out.println("twos: " + new Integer(twosCount));
}

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

``````public static void numberOfTwos(int n) throws Exception
{
int twosCount = 0;
int factor    = 0;

if( n < 0 )
{
throw new Exception();
}

while( n != 0 )
{
int lsd = n % 10;

twosCount += lsd * factor;

if( lsd >= 2 )
{
twosCount++;
}

n /= 10;
factor = factor * 10 + 1;
}

System.out.println("twos: " + new Integer(twosCount));
}``````

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

``````public static void numberOfTwos(int n) throws Exception
{
int twosCount = 0;
int factor    = 0;

if( n < 0 )
{
throw new Exception();
}

while( n != 0 )
{
int lsd = n % 10;

twosCount += lsd * factor;

if( lsd >= 2 )
{
twosCount++;
}

n /= 10;
factor = factor * 10 + 1;
}

System.out.println("twos: " + new Integer(twosCount));
}``````

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

#include<stdio.h>
#include<conio.h>
int main()
{
int a[20],c,n,r,i;
c=0;
printf("\n enter the no. of integers you wamt to insert:");
scanf("%d",&n);
printf("\n enter the no. of integers:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n the no. of 2s are:");
i=0;
while(i<n)
{
while(a[i]!=0)
{
r=a[i]%10;
if(r==2)
c++;
a[i]=a[i]/10;
}
i++;
}
printf("%d",c);

getch();
}

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

#include<stdio.h>
#include<conio.h>
int main()
{
int a[20],c,n,r,i;
c=0;
printf("\n enter the no. of integers you wamt to insert:");
scanf("%d",&n);
printf("\n enter the no. of integers:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n the no. of 2s are:");
i=0;
while(i<n)
{
while(a[i]!=0)
{
r=a[i]%10;
if(r==2)
c++;
a[i]=a[i]/10;
}
i++;
}
printf("%d",c);
getch();
}

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

``````#include<stdio.h>
#include<conio.h>
int main()
{
int a[20],c,n,r,i;
c=0;
printf("\n enter the no. of integers you wamt to insert:");
scanf("%d",&n);
printf("\n enter the no. of integers:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n the no. of 2s are:");
i=0;
while(i<n)
{
while(a[i]!=0)
{
r=a[i]%10;
if(r==2)
c++;
a[i]=a[i]/10;
}
i++;
}
printf("%d",c);
getch();
}``````

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

it is actually o(1) solution

``````function(int N)
{
inf half = floor((float)N/2);
return half * (half + 1) /2;``````

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

Here is my code in C++.
Starting from the most significant digit,
count the number of 2s appeared in the digit.

``````using ulong = unsigned long long;

ulong count2Range(ulong n)
{
string N = to_string(n);
ulong cnt = 0;

for(int pos = 0; pos < N.size(); pos++){
int digit = N.size() - 1 - pos;
// count contribution at the digit
// while counting upto [0...pos] * 10^i
if(pos != 0){
ulong t = atoi(N.substr(0, pos).c_str());
cnt += t * pow(10, digit);
}

// after [0...pos] * 10^i
if(N[pos] - '0' >= 3){
cnt += pow(10, digit);
}
else if(N[pos] - '0' >= 2){
cnt += 1;
if(pos != N.size() - 1)
cnt += atoi(N.substr(pos + 1).c_str());
}
}

return cnt;
}``````

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

Using regex library of python.

``````import re

pattern=re.compile("2")
MAX_DIGIT=200;
occ=0;
for i in range(0,MAX_DIGIT+1):
occ+=(len(pattern.findall(str(i))))
print(occ)``````

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.