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