一道據說是Google的面試題
題目:有一個整數n,寫一個函數f(n),返回0到n之間出現的"1"的個數。比如f(13)=6 ; f(11)=4,算出f(n)=n的n(如f(1)=1)？
我用python寫了一份代碼,還改寫了一份c++代碼
python源代碼
def count(i):
"""count form 0 to this number contain how many 1
1.you shoul know pow(10,n)-1 contain 1 number is n*pow(10,n-1)
2.use 32123 for example:
from 10000 to 32123 the first digit contain 1 number is 1(0000-9999) = pow(10,4) ,
and from 10000 to 30000 the rest digit contain 1 number is ( firstDigit*4*pow(10,4-1) )
so count(32123)=pow(10,4)+( firstDigit*4*pow(10,4-1) ) + count(2123)
print count(1599985)
1599985
print count(8)
1
"""
if i==0:
return 0
if 9>=i>=1:
return 1
digit=len(str(i))
firstDigit=int(str(i)[0])
if firstDigit>1:
now=pow(10,digit-1)
else:
now=int(str(i)[1:])+1
now+=(digit-1)*pow(10,digit-2) * firstDigit
return now+count(int(str(i)[1:]))
def little(i):
count_i=count(i)
if i<count_i:
#i reduce 1 , count_i at most reduce 9 ,
#so you at least reduce (count_i-i)/(9-1) to reach i==count_i
#用位數更快
if (count_i-i)/8>1:
return i-(count_i-i)/8
if i>count_i:
#i reduce 1 , count_i at least reduce 0 , so you at least reduce (i-count_i) to reach i==count_i
return count_i
return i-1
def run(i=10*10**(10-1)):
while i>0:
# print i,'=>i-count_i= ',i-count(i)
if i==count(i):
print i,','
i=little(i)
def fastrun(t=10*10**(10-1)):
"""This just list out all this king of element :) But it is fastest and most useful"""
all=[1, 199981, 199982, 199983, 199984, 199985, 199986, 199987, 199988, 199989, 199990, 200000, 200001, 1599981, 1599982, 1599983, 1599984, 1599985, 1599986, 1599987, 1599988, 1599989, 1599990, 2600000, 2600001, 13199998, 35000000, 35000001, 35199981, 35199982, 35199983, 35199984, 35199985, 35199986, 35199987, 35199988, 35199989, 35199990, 35200000, 35200001, 117463825, 500000000, 500000001, 500199981, 500199982, 500199983, 500199984, 500199985, 500199986, 500199987, 500199988, 500199989, 500199990, 500200000, 500200001, 501599981, 501599982, 501599983, 501599984, 501599985, 501599986, 501599987, 501599988, 501599989, 501599990, 502600000, 502600001, 513199998, 535000000, 535000001, 535199981, 535199982, 535199983, 535199984, 535199985, 535199986, 535199987, 535199988, 535199989, 535199990, 535200000, 535200001, 1111111110]
for i in all:
if(t>=i):
print i
print "first test with run() to:111111111"
run(111111111)
print '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>'
print "2st test with run() to:10^10"
run()
print '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>'
print "3st test with fastrun() to:10^10 , Fastest!!!"
fastrun()
C++代碼
-------------------------------------------------------------------------------
#include <cmath>
#include <iostream>
using namespace std;
unsigned long long mypow(int a,int b)
{
unsigned long long sum=1;
for(int i=0;i<b;i++)
sum*=a;
return sum;
}
unsigned long long count(unsigned long long i){
/*
count form 0 to this number contain how many 1
1.you shoul know pow(10,n)-1 contain 1 number is n*pow(10,n-1)
2.use 32123 for example:
from 10000 to 32123 the first digit contain 1 number is 1(0000-9999) = pow(10,4) ,
and from 10000 to 30000 the rest digit contain 1 number is ( firstDigit*4*pow(10,4-1) )
so count(32123)=pow(10,4)+( firstDigit*4*pow(10,4-1) ) + count(2123)
*/
if(i==0)return 0;
if(9>=i and i>=1)return 1;
int digit=1;
unsigned long long firstDigit=i;
while(firstDigit>=10){
firstDigit/=10;
++digit;
}
unsigned long long now;
unsigned long long rest=static_cast<unsigned long long int>(i-(firstDigit*mypow(10,digit-1)));
if(firstDigit>1)now=static_cast<unsigned long long int>(mypow(10,digit-1));
else{now=rest+1;}
now+=static_cast<unsigned long long int>((digit-1)*mypow(10,digit-2) * firstDigit);
return (now+count(rest));
}
unsigned long long little(unsigned long long i)
{
unsigned long long count_i=count(i);
if(i<count_i){
//i reduce 1 , count_i at most reduce 9 , so you at least reduce
//用位數更快
(count_i-i)/(9-1) to reach i==count_i
if ((count_i-i)/8>1)return i-(count_i-i)/8;
}
if(i>count_i){
//i reduce 1 , count_i at least reduce 0 , so you at least reduce (i-count_i) to reach i==count_i
return count_i;
}
return i-1;
}
void run(unsigned long long i=pow(10.0f,10)){
while (i>0){
// print i,'=>i-count_i= ',i-count(i)
if(i==count(i))cout<<i<<"=>"<<count(i)<<'\n';
i=little(i);
}
cout<<"run() finished\n\n";
}
void fastrun(unsigned long long t=pow(10.0f,10)){
//This just list out all this king of element :) But it is fastest and most useful
const unsigned long long all[]={1, 199981, 199982, 199983, 199984, 199985, 199986, 199987, 199988, 199989, 199990, 200000, 200001, 1599981, 1599982, 1599983, 1599984, 1599985, 1599986, 1599987, 1599988, 1599989, 1599990, 2600000, 2600001, 13199998, 35000000, 35000001, 35199981, 35199982, 35199983, 35199984, 35199985, 35199986, 35199987, 35199988, 35199989, 35199990, 35200000, 35200001, 117463825, 500000000, 500000001, 500199981, 500199982, 500199983, 500199984, 500199985, 500199986, 500199987, 500199988, 500199989, 500199990, 500200000, 500200001, 501599981, 501599982, 501599983, 501599984, 501599985, 501599986, 501599987, 501599988, 501599989, 501599990, 502600000, 502600001, 513199998, 535000000, 535000001, 535199981, 535199982, 535199983, 535199984, 535199985, 535199986, 535199987, 535199988, 535199989, 535199990, 535200000, 535200001, 1111111110};
for(int i=0;i!=83;++i){
if(t>=all[i])cout<<all[i]<<'\n';
}
cout<<"fastrun() finished\n\n";
}
int main(int argc, char *argv[])
{
for(;;)
{
unsigned long long i;
cout<<"please input a number:";
cin>>i;
cout<<"run():\n";
run(i);
cout<<"fastrun():\n";
fastrun(i);
}
system("PAUSE");
return EXIT_SUCCESS;
}