## Microsoft Interview Question

Development Support Engineers#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);

}

// 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

// 2...add if yes

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;

}

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

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.

#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");

}

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)

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!

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)

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;
}
```

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

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
# the desired answer.
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
```

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)

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

```
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);
}
}
```

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);

}

```
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);
```

}

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);
return total;
}
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;
return total;
}
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);
}
return total;
}
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;
}
```

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;

}

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

al.Add(pattern1);

pattern1 = pattern1 + 10;

}

while (pattern2 <= range)

{

// Pattern2: 20, 120, 220, 320, 420, 520, 620, 720, 820, 920, 1020, etc...

al.Add(pattern2);

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;

al.Add(pattern3);

pattern3++;

}

pattern3 = pattern3 + 100 - 8;

}

else

{

while (pattern3 <= range)

{

if (count != 2)

{

al.Add(pattern3);

}

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);

}

We can use the following pattern:

- Amit November 23, 20082 @ 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