A Different Thinking Process for "Count the number of two's from 1 to n"
Careercup-150 solves this problem by this approach:
Pattern: 0-10: 1 2s; 0-100: 20 2s; 0-1000: 300 2s; between 0 and 10^n, there are n*(10^n-1) 2s. Let f(n)=n*(10^n-1), we have: between 0 and x*10^n, number of 2s becomes:
Think of the problem as your car pedometer, the numbers roll up, over and push the next column. Patter: every 10 miles, the digit for 2 rolls once; Every 100 miles, the 10's digit rolls 2 10 times; Every 1000, the 3rd digit rolls 2 100 times. Take the number 2145, starting from 5 as p0 slot, we have p3p2p1p0 four slots. Number of 2's occurred for each slot would be:
Code(shorter than Careercup hooray!)
public static int CountTow(int n) {
int sum = 0;
int temp = n;
int base = 1;
while(temp>10) {
sum += base * temp/10 + (temp%10>1? 1:0);
temp = temp/10;
base*=10;
}
if (temp==2) {
sum += (n-2*base+1);
}else if(temp >2) {
sum += base;
}
return sum;
}
Unitest
CountTow(-1) - 0
CountTow(0) - 0
CountTow(1) - 0
CountTow(2) - 1
CountTow(12) - 2
CountTow(20) - 3
CountTow(29) - 13
CountTow(100) -20
CountTow(1000) -300
CountTow(2145) -786
Careercup-150 solves this problem by this approach:
Pattern: 0-10: 1 2s; 0-100: 20 2s; 0-1000: 300 2s; between 0 and 10^n, there are n*(10^n-1) 2s. Let f(n)=n*(10^n-1), we have: between 0 and x*10^n, number of 2s becomes:
- x>2 -- x*f(n) + 10^(n-1)
- x=2 -- x*f(n) + 1
- x<2 -- f(n-1)
Think of the problem as your car pedometer, the numbers roll up, over and push the next column. Patter: every 10 miles, the digit for 2 rolls once; Every 100 miles, the 10's digit rolls 2 10 times; Every 1000, the 3rd digit rolls 2 100 times. Take the number 2145, starting from 5 as p0 slot, we have p3p2p1p0 four slots. Number of 2's occurred for each slot would be:
- p0: (214+1)*1 //pedometer slot 0 was rolled from 0-9 214 times, plus 1 to reach 5
- p1: (21+1)*10 //pedometer slot 1 was in 2 position for 22 times, which includes rolling 0-9 for 21 times, and 1 time before it reaches 4
- p2: 2*100 //pedometer slot 2 was rolled from 0-9 2 times, i.e., 200-299, and 1200-1299.
- p3: 146 //bcoz p3=2 and p3 is the highest slot, this slot has stayed at 2 from 2000 for 146 times.
Code(shorter than Careercup hooray!)
public static int CountTow(int n) {
int sum = 0;
int temp = n;
int base = 1;
while(temp>10) {
sum += base * temp/10 + (temp%10>1? 1:0);
temp = temp/10;
base*=10;
}
if (temp==2) {
sum += (n-2*base+1);
}else if(temp >2) {
sum += base;
}
return sum;
}
Unitest
CountTow(-1) - 0
CountTow(0) - 0
CountTow(1) - 0
CountTow(2) - 1
CountTow(12) - 2
CountTow(20) - 3
CountTow(29) - 13
CountTow(100) -20
CountTow(1000) -300
CountTow(2145) -786

0 Comments:
Post a Comment
<< Home