fork(1) download 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <cstdlib>
  4. using namespace std;
  5. long long f[20];
  6. int count(int n) {
  7.   int count = 0;
  8.   int factor = 1;
  9.   int pos = 0;
  10.   while (true) {
  11.     int m = n / factor;
  12.     if (m == 0) //Past last digit
  13.       break;
  14.     int d = m % 10;      
  15.  
  16.     count += d * pos * factor / 10; 
  17.  
  18.     if (d == 2)
  19.       count += n % factor;
  20.     else if (d > 2) {
  21.       count += factor; 
  22.     }
  23.  
  24.     factor = 10 * factor;
  25.     pos++;
  26.   }
  27.  
  28.   return count;
  29. }  
  30. int twos(int n , int k)
  31. {
  32.     if(n<2)
  33.         return 0;
  34.     else if(n<10)
  35.         return 1;
  36.  
  37.     int msb = n/(int)pow(10,k);
  38.     int remainder = n%(int)pow(10,k);
  39.  
  40.     if(msb==2) // eg 230 ,  calculate 200 ... to 230  , and find twos from 0 on 199  and recursion on 30
  41.         return msb*(f[k]) + (remainder+1) + twos(remainder,k-1); // 2*(below 100) + 31 + tows(30)
  42.     else if (msb>=3)
  43.          return msb*(f[k]) + pow(10,k) + twos(remainder,k-1);  // for 312 -> 3*(below 100) + 100 + twos(12)
  44.     else
  45.         return  msb*(f[k]) + twos(remainder,k-1);
  46.  
  47. }
  48.  
  49. int brute(int n)
  50. {
  51. 	int cnt=0;
  52.     for(int i=1 ; i<=n;i++)
  53.     {
  54.     	int j=i;
  55.     	while(j)
  56.     	{
  57.     		cnt+=(j%10==2)?1:0;
  58.     		j/=10;
  59.     	}
  60.     }
  61. return cnt;
  62. }
  63.  
  64.  
  65. int main()
  66. {
  67.  
  68. int i,j,k;
  69.   f[1] = 1;
  70.   for(i=2;i<=18;i++)
  71.      f[i]=10*f[i-1] + pow(10,i-1);
  72.  
  73. srand(NULL);
  74.  
  75.   for(i=2 , j=1;  i< 100000000 ;  i+=(rand()%((int)pow(10,j))) , j++ )
  76.   	cout<<i<<"  " <<count(i)<<"  "<< twos(i,j)<<"  \n";
  77.  
  78.  
  79.  
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0s 3296KB
comments (?)
stdin 
Standard input is empty
stdout 
2  0  1  
5  1  1  
91  19  19  
868  277  277  
7783  3359  3359  
55576  32718  32718  
293911  242092  242093  
10179297  7091857  7091858  
59939789  51975959  51975959
https://ideone.com/ewOc49
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!