薯队长在平时工作中需要经常跟数字打交道,某一天薯队长收到了一个满是数字的表格,薯队长注意到这些数字里边很多数字都包含1,比如101里边包含两个1,616里包含一个1。
请你设计一个程序帮薯队长计算任意一个正整数n(0<n<=2147483647),从1到n(包括n)的所有整数数字里含有多少个1。
正整数n(0<n<=2147483647)
从1到n(包括n)的所有整数数字里含有多少个1
1
1
13
6
从1到13(包括13)有13个数字,其中包含1的数字有1,10,11,12,13,这些数字里分别有1,1,2,1,1个1,所以从1到13(包括13)的整数数字中一共有1+1+2+1+1=6个1
def NumberOf1Between1AndN_Solution(n): mult, sumTimes = 1, 0 while n//mult > 0: high, mod = divmod(n, mult*10) curNum, low = divmod(mod, mult) if curNum > 1: sumTimes += high*mult + mult elif curNum == 1: sumTimes += high*mult + low + 1 else: sumTimes += high*mult mult = mult*10 print(sumTimes) if __name__ == '__main__': n = int(input()) NumberOf1Between1AndN_Solution(n)
#include<iostream> using namespace std; int main() { long long res = 0,n; long long left=0, right = 0, base = 1; cin>>n; if(n<=0) cout<<0<<endl; else{ while (n>=base) { left = n/base; right = n%base; if((left%10)>1) res+= (left/10+1)*base; else if((left%10)==1) res+=(left/10)*base+(right+1); else res+=(left/10)*base; base *=10; } cout<<res<<endl; } return 0; }
#include <iostream> using namespace std; int main() { long long n; cin>>n; long long num_1; long long tmp=n; long long multi=1; while(tmp>0) { int left=n%multi; num_1+=(tmp/10)*multi; if(tmp%10>1) num_1+=multi; else if(tmp%10==1)num_1+=left+1; multi*=10; tmp=tmp/10; } cout<<num_1<<endl; return 0; }
n = input() m = len(n) def turn(s): if s: return int(s) return 0 ans = 0 for i in range(m): if n[i] > '1': ans += (turn(n[:i]) + 1) * 10 **(m-i-1) elif n[i] == '1': ans += (turn(n[i+1:]) + 1) + turn(n[:i]) * 10 ** (m-i-1) else: ans += turn(n[:i]) * 10 ** (m-i-1) print(ans)
package com.shenyue.beedi.controller; import java.util.Scanner; public class Test { public static void main(String[] args) { System.out.println("请输入一个数字"); Scanner in = new Scanner(System.in); int num = in.nextInt(); int count = 0; for(int i=1;i<=num;i++){ String s = Integer.toString(i); String[] numArr = s.split(""); for (String s1 : numArr) { if(s1.equals("1")){ count++; } } } System.out.println(count); in.close(); } }
//左神书中原题,时间复杂度O(logN*logN) #include <cmath> #include <iostream> using namespace std; int getlength(int num){ int len=0; while (num>0){ ++len; num/=10; } return len; } long getCount(int num){ if (num<1) return 0; int len=getlength(num); if (len==1) return 1; long tmp=pow(10,len-1); int first=num/tmp; int fcount= first==1? num%tmp+1 : tmp; long othercount=first*(len-1)*(tmp/10); return fcount+othercount+getCount(num%tmp); } int main(){ int num; long ans; cin>>num; ans=getCount(num); cout<<ans<<endl; return 0; }