## Microsoft Interview Question for Development Support Engineers

• 0

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

We can use the following pattern:
2 @ unit's digit adds 1 '2' every 10 numbers (1/10)
2 @ TEn's place adds 10 '2' every 100 numbers (10/100)
2 @ hundred's place: 100/1000
and so on

So, we simply divide n by increasing powers of 10 until n/10^x < 1
in that case we check

if n>=3*10^(x-1) count+=10^(x-1)
else if n>=2*10^x-1 && n<3*10^x-1 count+=n-2*10^(x-1)+1

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

thought on the same line...it works...

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

#include<stdio.h>

int main()
{
int n,i,j;
int ctr=0;
scanf("%d",&n);
for(i=0;i<=n;i++)
{
for(j=i;j>0;j=j/10)
{
if((j%10)==2)
ctr++;
}

}

printf("The number of 2's is >> %d ",ctr);

}

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

what about 20%10 = 0 ... it'll not count this similarly 120%10 .... and so on ...

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

totally wrong solution ....

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

This gives the right solution!

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

// returns no of 2's in values <= no...takes in only multiples of 10 starting from 10...

int getTwoCountFor10Multiples(int no)
{
int retVal = no/10;
if (no != 10 )
return retVal + (no/10) - 1;
else
return retVal;

}

void find2Count(int n)
{
int temp = n;
int start = 1;
int retVal = 0;

while(temp != 0)
{
// get the value....
int val = temp%10;

// if no units place...find number of ones for the 10th power you are
// at...and add it by val times...
if (start != 1)
retVal = retVal + val*getTwoCountFor10Multiples(start);
else if (val >= 2) // if units place...just see if greater than
retVal += 1;

// move temp and start accordingly
temp = temp/10;
start = start*10;

}

// for nos like 50...above while will give 5 times no of 2s less than 10...

// this snippet will accomodate for all 2's in 10s place of 20
int base = 2*(start/10);
if ( n >= base )
if ( n <= (base + (start/10) - 1) ) // if between 20 and 30
retVal += n - base + 1;
else
retVal += (start/10) - 1; /// if greater than 30

cout<<retVal;
}

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

getTwoCountFor10Multiples(int no)

if (no != 10 )
return retVal + (no/10) - 1;

should be
if (no != 10 )
return retVal + (no/10);

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

king_k - Can you explain your solution?

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

convert the no into string
search for 2

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

Converting the number into string would require the same logic of collecting the remainder and dividing by 10

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

Not necessarily, use sprintf() or itoa() functions.

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

Here is my algorithm...
each 10 contributes 1 2.

This is what the while loop does...
216:
6 --> 1 two before that

16 --> Consider 10 --> 1 two there

216 --> Consider 100 --> There is (100/10) 10's...each gives one 2...so 10...now below 100...there is also the whole 20 series...which has 10 occurences of 2...So each hundered gives 20 2s...
So this happens for 0-100 and 100-200...So multiply 20 by 2....40

Total so far 42.

Now, 216 also has a 2 for each number between 200 and 216...thats considered in the final snippet after the while loop...Look for 200-300.

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

unsigned int Count2th(unsigned int number)
{
unsigned int count = 0;
while (number > 1)
{
if (number == 2)
return count + 1;
unsigned int n = number;
while (n)
{
unsigned int rem = n % 10;
if (rem == 2)
++count;
n /= 10;
}
--number;
}
return count;
}

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

#include <stdio.h>
#include <string.h>
#define NUMBER 200
main ()
{
/*This program calculates the number of 2's present in the number x*/

int arr[NUMBER];
int i=0,count=0;
while(i<NUMBER)
{
arr[i]=i+1;
printf("%d ",arr[i]);
i++;
}
for(i=0;i<NUMBER;i++)
{
while(arr[i]>0)
{
int rem,quo;
rem=arr[i]%10;
quo=arr[i]/10;
if(rem==2&&quo==2)
{
count=count+2;

printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;

}
else if(rem==2)
{
count++;
printf("Number is : %d\n",arr[i]);
}
else if(quo==2)
{
count++;
printf("Number is : %d\n",arr[i]);
arr[i]=arr[i]/10;
}
arr[i]=arr[i]/10;
}
}
/* complexity of this program : n* size of the number ( digits present in the number*/
/* Worst case O(n^2)*/

printf("\n\n\n");
printf("THe number of 2's are : %d\n",count);
printf("\n\n\n");
}

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

int Find2s_(int r1, int r2)
{
int count2 = 0;
for (int i = r1; i <= r2; i++)
{
count2 += SplitNumberCacl2(i);
}
return count2;
}

int SplitNumberCacl2(int n)
{
if (n <= 0)
return 0;
int countTwo = 0;
while(true)
{
int rem = n % 10;
if (rem == 2)
countTwo++;
n = (n - rem) / 10;
if (n == 0)
break;
}

return countTwo;

}

this is O(n) not o(n^2) because the max value of int is 2,147,483,647 so thats the worst case with 10 iterations so its O(10n) = o(n)

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

No, the max value of integer can be 18446744073709551615 (if you define the integer as unsigned long long)which is of size 20..so the order would be O(20.n)

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

int main( )
{
long range,count,temp,sum=0;

cout<< "Enter the range :";
cin>>range;

for (count=0;count<=range;count++)
{
temp=count;
while(temp>0)
{
if(temp%10==2)
sum++;
temp/=10;
}
}

cout<<"The number of 2s is "<<sum<<endl;

return 0;
}

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

int Count2th(unsigned int num)
{
int count = 0;
while(num)
{
int n = num;
while(n)
{
char ch = n%10 + '0';
if (ch == '2')
count++;
n /= 10;
}
num--;
}
return count;

}

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

Havent given it much thought but how about converting the number to a string and then using string operation to find the number of 2s in it. String compare should be better than division i feel....

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

firstly:take a simple question: how many 2 between [ 1000, 2000 )?
ans is quite obvious, ( (2000-1000)*3 )/10 = 300
then how many 2 between [ 10000, 20000 )?
ans is quite obvious, ( (20000-10000)*4 )/10 = 4000
see the pattern?

now let's see how many 2 between [ 0, 1000 )?
[ 0, 1000 ) --> [ 0, 900) + [ 900, 1000 )
[ 0, 900 ) --> [ 0, 100) + [ 100, 200 ) + [ 200, 300 ) .... + [ 800, 900 )
divide and conquer.
I think my idea is helpful.
any comment is welcome!

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

This kind of problem should be answered based on how 2 can appear
in a range,at unit place,at tens place etc
It is middle school permutation/combination problem.

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

Dont just confine to 2 - Think in the terms of digit 'd' in the range [0-n]
We can get a recurrence relation.

100[w=n%10000?10:0 + ......] + 10[z=n%1000)>d?10:0 + z] + [(y=n%100)>d?10:0 + y]+[(x=n%10)>d?1:0]

One catch in the above approch is if for some 'x' (different from the above context) (x = n%100) == d, then you can't add 10, you need to see the n%10 and add Total number of 'd's = (n%10+1)

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

This is what I came up with:

``````#include <iostream>
using namespace std;

int count_digit(int n, int dig)
{
int count = 0;
while (n)
{
int q = n / 10;
int remainder = n - q * 10;
if (remainder == dig)
{
++count;
}
n = q;
}
return count;
}

void main()
{
int count = 0;
for (int i = 0; i != 35; ++i)
{
count += count_digit(i, 2);
}
cout << count << endl;
}``````

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

i think cristi.vlasceanu 's solution is fine, would you please explain the approach a bit? @ cristi.vlasceanu

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

Whats there to explain in this ?

Rewinding back to our school days, Formulae: [ Dividend = Divisor * Quotient + Reminder ]

In the count_digit function, Cristi has used this formulae to get very single digit in a number and then check if it 2.

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

int count2(int n) {
int rem = n % 10;
//count2(head-1)*10 count all 2s originated from the higher position
//head count all 2s originated from the current position
if (rem > 2) return value+1;
else return value;
}

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

oh, forget the ending condition:
if (n == 0) return 0;

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

Python implementation: fast version checked against slow version for n up to 10000.

``````def count_digits_dumb(d, n):
sd = str(d)
return sum(str(i).count(sd) for i in range(n+1))

def count_digits_smart(d, n, ns, k):
if not k:
return 0
b = int(ns[0]) # leading (position k) digit of n
p = 10**(k-1)
cnt = b*(k-1)*(p//10) # count d at non-k digit positions
if b > d: # count all d at leading position
cnt += p
elif b == d: # count partial d at leading position
cnt += n-d*p+1

# At this point we have accounted for all d on digit position k
# and all d below b*p, so we are reduced to the sub-problem
# on [0, n-b*p], where n-b*p is k-1 digits long. So just apply
# recursion and sum up all the counts on the way back up to get
return cnt + count_digits_smart(d, n-b*p, ns[1:], k-1)

d = 2
n = 1234321
ns = str(n)
k = len(ns)
print(count_digits_dumb(d, n))
print(count_digits_smart(d, n, ns, k))
# ans: 758686``````

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

simple solution : DP

store 1 digit number having 2 : 2
store 2 digit number having 2 : appending 0-9 after 2 and appending 1-9 before 2
store 3 digit number having 2: appending 0-9 after abv 2 digit numbers and appending 1-9 before abv 2 digit number

go on like this this till number of digits <= number of digts in n and number<n..

Answer in constant order if u get nay number less than n(for other test cases)

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

not constant but O(number of digits of n)

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

<pre lang="python" line="1" title="CodeMonkey56705" class="run-this">#!/usr/bin/python

import sys

def numOf2Dumb(num):
count = 0
for n in range(num):
x = str(n)
for t in x :
if t == '2':
count+=1
return count

def numOf2Smart(num):
count = 0
n1 = str(num)
n = n1[::-1] #reverse the string
t1 = 0
t2 = 1
l = len(n)
for i in range(l):
y = int(n[i])
count += (y*t1)
if y > 2 :
count += t2
elif y == 2 :
if l>i and i>0:
count += int(n1[l-i:])
t1, t2 = t2+10*t1, t2*10

return count

# Gather our code in a main() function
def main():
print numOf2Dumb(120)
print numOf2Smart(120)

# Standard boilerplate to call the main() function to begin
# the program.
if __name__ == '__main__':
main()

</pre><pre title="CodeMonkey56705" input="yes">1
2
10
42
11

</pre>

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

interviewcodesnippets.com/2010/09/counting-2s-brute-force/

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

``````public int CountNumberOf2s(int n)
{
int count=0;
if (n < 0)
return -1;
else
{
string temp;
for (int i = 2; i <= n; i++)
{
int j = 0;
temp = i.ToString();
while (j < temp.Length)
{
if (temp[j] == '2')
{
count++;
}
j++;
}
}
}
return count;
}``````

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

``````public class NumOfTwosBetZeroAndN {
static int count = 0;
public static void main(String[] args) {
// TODO Auto-generated method stub
//int b;
int []a = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};
for(int i=0;i<a.length;i++)
{
if(a[i]==0)
{
count=0;
}
else {
while((a[i]%2)==0)
{
count++;
a[i] = a[i]/2;
}
}
}
System.out.println("total number of 2's between 0 and n are: " +count);
}

}``````

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

function findLength(n){

var arr = [];
while(n > 9)
{
var no = n%10;
arr.push(no);
n = n/10;
n = parseInt(n);
}
arr.push(n);
return arr.length;
}

function find2(n){
var l = findLength(n);
if(l == 1){
if(n > 1)
return 1;

return 0;
}
var f = parseInt(n/ (Math.pow(10, l-1)));
var two = Math.pow(10, l-2) * (l-1);
var count = 0;
if(f == 2){
count = 2 * two + (n - 2 *(Math.pow(10,l-1))) + 1;
}
else{
if(f < 2){
count = two;
}
if(f >= 3){
count = ((f ) * two) + (Math.pow(10, l-1));
}
}
count = count + find2(n % (Math.pow(10, (l-1))));
return count;
}

function find2Test(n){
var c = 0;
var i = 2;
function count2(number){

while(number > 1)
{
var no = number%10;
if(no == 2){
c++;
}
number = number/10;
number = parseInt(number);
}

}

while(i <= n){
count2(i);
i++;
}
return c;
//console.log(c);
}
function executeBoth(n){
console.log(find2 (n),find2Test(n));
}
function runTest(n){
return find2(n) == find2Test(n);
}

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

``````function findLength(n){

var arr = [];
while(n > 9)
{
var no = n%10;
arr.push(no);
n = n/10;
n = parseInt(n);
}
arr.push(n);
return arr.length;
}

function find2(n){
var l = findLength(n);
if(l == 1){
if(n > 1)
return 1;

return 0;
}
var f =  parseInt(n/ (Math.pow(10, l-1)));
var two = Math.pow(10, l-2) * (l-1);
var count = 0;
if(f == 2){
count = 2 * two + (n - 2 *(Math.pow(10,l-1))) + 1;
}
else{
if(f < 2){
count = two;
}
if(f >= 3){
count = ((f ) * two)  + (Math.pow(10, l-1));
}
}
count = count + find2(n % (Math.pow(10, (l-1))));
return count;
}

function find2Test(n){
var c = 0;
var i = 2;
function count2(number){

while(number > 1)
{
var no = number%10;
if(no == 2){
c++;
}
number = number/10;
number = parseInt(number);
}

}

while(i <= n){
count2(i);
i++;
}
return c;
//console.log(c);
}
function executeBoth(n){
console.log(find2 (n),find2Test(n));
}
function runTest(n){
return find2(n) == find2Test(n);``````

}

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

I was trying this today and came up with recursive solution for this-
you can check the logic:
start with the leftmost digit and find the number of 2 with the leftmost digit and the
remainder has to be calculated again to find number of 2, I also added the iterative version to check the correct answer
so we can verify it is correct(as every time the number is reduced to 1/10 of the number it is log(n) solution):

``````#include <iostream>
#include <cmath>
using namespace std;

long calcD(long rem){
long count = 0;
while(rem){
count++;
rem /= 10;
}
return count;
}

long q(long m, long z){
long total = 1;
long i = 1;
while(i < z){
total = total * 10 + pow(10, i);
i++;
}
total = total * m;
if(m > 2)
total += pow(10, z);
}

long pow10L(long p){
long ans = 1;
while(p--){
ans *= 10;
}
return ans;
}

long f(long n, long d){
if(d == 1)
return n >= 2 ? 1 : 0;
long msd = n / pow10L(d - 1);
long rem = n % pow10L(d - 1);
//cout << "method f" << n<< " msd " << msd << " rem "<< rem << endl;
long total = 0;
if(rem == 0)
total += q(msd, d - 1) + (msd == 2 ? 1 : 0);
else if(msd > 2)
total += q(msd, d-1) + f(rem, calcD(rem));
else if(msd == 2)
total += q(msd, d - 1) + rem + 1 + f(rem, calcD(rem));
else
total += q(msd, d - 1) + f(rem, calcD(rem));
//cout << "method f" << n << " =" << total << endl;
}

long find2(long n){
int count = 0;
while(n){
if(n % 10 == 2)
count++;
n /= 10;
}
return count;
}

long iterative(long n){
long total = 0;
for(long i = 2; i <= n; i++){
total += find2(i);
}
}

int main() {
cout << "enter the n: ";
long n;
cin >> n;
cout << "The answer is from method: " << f(n, calcD(n)) <<  endl;
cout << "The answer is from iterative: " << iterative(n) <<  endl;
return 0;
}``````

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

The cheap (and dirty) way would be create an array from 1-n. As you are creating it, inspect each number and see if it has a '2' in it. I agree, its not optimal.

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

range num_of_twos
0~99 20
100~199 20
...
900~999 20

so
0~999 20*10
1000~1999 20*10
...
9000~9999 20*10
...
//======================
#define num_of_twos 20

int countTwo(int num)
{
int count=0,mod1=0,mod2=0,mod=0;
int scale=1;
mod1=num%10;
num=num/10;
mod2=num%10;
num=num/10;

while(num>0)
{
mod=num%10;
num=num/10;
count=count+mod*num_of_twos*scale;
}

if(mod2<2)//less than 20
{
if(mod1>=2)
count+=mod2+1;
else
count+=mod2;
}
else if(mod2>2)//bigger than 29
{
if(mod1>=2)
count+=mod2+10+1;
else
count+=mod2+10;
}
else
{
if(mod1>=2)//between 20~29
count+=mod2+mod1+2;
else
count+=mod2+mod1+1;

}
return count;

}

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

This is absolutely not correct. from 200 to 299, there are 120 2's.

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

This is absolutely not correct. from 200 to 299, there are 120 2's.

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

This is absolutely not correct. from 200 to 299, there are 120 2's.

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

Pattern idea is perfect.
Here is the code.

Total count of 2 in the range
2's count in 1-100 = 19
2's count in 1-1000 = 190
2's count in 1-2000 = 380
2's count in 1-4000 = 760
2's count in 1-8000 = 1520

/*
Write a method to count the number of 2's between 0 and n.
EXAMPLE
input: 35
output: 13 [list of 2's: 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32]
*/
public static string CountNumberOf2sInGivenRange(int range)
{
// Few assumptions: Range is unssigned value
if (range < 1) return "0";

int pattern1 = 2;
int pattern2 = 20;
int pattern3 = 21;
ArrayList al = new ArrayList();

while (pattern1 <= range)
{
// Pattern1: 2, 12, 22, 32, 42, 52, 62, 72, 82, 92, 102, 112, 122, etc....
pattern1 = pattern1 + 10;
}

while (pattern2 <= range)
{
// Pattern2: 20, 120, 220, 320, 420, 520, 620, 720, 820, 920, 1020, etc...
pattern2 = pattern2 + 100;
}

while (pattern3 <= range)
{
// Pattern3: 21, 23, 24, 25, 26, 27, 28, 29, 121, 123, 124, 125, 126, 127, 128, 129, 221, 223, etc...
int count = 1;
if (pattern3 + 8 <= range)
{
for (int i = 1; i <= 9; i++)
{
if (i == 2) continue;
pattern3++;
}

pattern3 = pattern3 + 100 - 8;
}
else
{
while (pattern3 <= range)
{
if (count != 2)
{
}

count++;
pattern3++;
}
}
}

string returnStr = string.Empty;
foreach (int i in al)
{
returnStr += i.ToString() + ", ";
}

return "Total count of 2 = " + al.Count + " : " + returnStr.Substring(0, returnStr.Length - 2);
}

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

There is actually 20 2s between 0-100. You are probably not counting that there are two 2s in `22`.

02, 12, 22, 32, etc.. = 10 in the 1s column
20, 21, 22, 23, 24 = 10 in the 10s from 20-29

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

The output should be 14 instead of 13, someone has to change it.

/*
Write a method to count the number of 2's between 0 and n.
EXAMPLE
input: 35
output: 13 [list of 2's: 2, 12, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 32]
*/

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.