[I tried Google's entrance exam (unofficial)](http://yasigani-ni.com/every-day/google%E3%81%AE%E5%85%A5%E7%A4%BE% E8% A9% A6% E9% A8% 93% E9% 9D% 9E% E5% 85% AC% E5% BC% 8F% E3% 81% AB% E3% 83% 81% E3% 83% A3% E3% 83% AC% E3% 83% B3% E3% 82% B8% E3% 81% 97% E3% 81% A6% E3% 81% BF% E3% 81% 9F /)
I tried it with java.
If you use a function that counts the number of 1s that appear, the amount of calculation increases as the number increases, so it is efficient to calculate sequentially without making it a function.
hoge.java
class hoge{
public static void main(String[] args) {
int ret =0;
for(int j=1;j<Integer.parseInt(args[0]);j++){
ret +=((" "+j+" ").split("1").length-1);
if(j<=ret){
System.out.println(ret);
}
}
}
}
>java hoge 200000
1
199981
199982
199983
199984
199985
199986
199987
199988
199989
199990
199992
199993
199994
199995
199996
199997
199998
199999
200000
199981
Since there is a calculation, I feel that it can be speeded up by exchanging numbers, but I stopped because it did not appear in the formula.
Alternatively, it may be faster to derive an approximate expression and then guess. If you don't use the library, it will take time.
Recommended Posts