# Finding pattern based solution Java

• When we have 1 digit (0-9) the maximum number of ones is 1
When we have 2 digits (0-99) the maximum number of ones is 20
When we have 3 digits (0-999) the maximum number of ones is 300
We see a pattern emerging 1,20,300,4000,50000,600000, ....
Looking for further patterns...

``````100,000 => 50,000+1
110,000 => 50,000+1+10,000  + 4000+1
120,000 => 50,000+1+20,000  + 4000*2+10,000

1,000,000 => 600,000+1
1,100,000 => 600,000+1+100,000  +  50,000+1
1,200,000 => 600,000+1+200,000  +  50,000*2+100,000

1,210,000 => 600,000+1+210,000  +  50,000*2+100,000  +  4,000+1
1,220,000 => 600,000+1+220,000  +  50,000*2+100,000  +  4,000*2+10,000
2,130,005 => 600,000*2+1,000,000  +  50,000+30,005+1  +  4,000*3+10,000   +  0*5 +1
``````

A clear pattern is emerging. Only non-zero digits matter, and 1's are to be handled differently from other non-zero digits. We can now come up with a formula, and put it into code.

`````` public class Solution {
public int countDigitOne(int n) {
int count = 0;
if (n>0){
String sValue = String.valueOf(n);
int length = sValue.length();

for (int i=0;i<length;i++){
int val = sValue.charAt(i) - '0';
int pow= length-i-1;
if (val == 1){
count = count + (int)Math.pow(10,pow-1)*pow +1;
if (i<(length-1)){
count = count + Integer.parseInt(sValue.substring(i+1));
}
}
else if (val >0){
count = count + (int)Math.pow(10,pow-1)*pow*val + (int)Math.pow(10,pow);
}
}
}
return count;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.