2 3 5 4
In each 100 to 999, we will have X 2s, so 2000 will give us 2 * X 2s. In 2000, we will have another 355 2s because of the 4th digit from 2000 to 2354, and the rest comes from 354. So the function looks like:
2 * numTwos(999) + numTwos(354) + 354 + 1
What if we have 3354 instead of 2354?
Now from 2000 to 2999, we will have 1000 2s. So the function becomes:
3 * numTwos(999) + numTwos(354) + 1000
Yep, a simple recursive solution would help.
public static int numTwos(int n){ if(n < 2) return 0; if(n < 10) return 1; int power = 1; while(10 * power <= n) power *= 10; int first = n / power; int reminder = n % power; int firstPart = 0; if(first > 2) firstPart += power; else if (first == 2) firstPart += reminder + 1; int secondPart = first * numTwos(power - 1) + numTwos(reminder); return firstPart + secondPart; }
No comments:
Post a Comment