Post date: Feb 02, 2014 10:49:8 AM
Question
Count the number of positive integers less than N that does not contains digit 4.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Count the number of positive integers less than N that does not contains digit 4.-- Google
Created Date : 02-02-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
int CountHelp(int n)
{
int total{ 0 };
int i = 1;
if (n <= 3){
return 0;
}
else if (n < 13){
return 1;
}
else{
while (n >= i * 10){
total += i + total * 8;
i *= 10;
}
return total;
}
}
int Count(int n)
{
int total{ 0 };
int i = 1;
while (i <= n) {
i *= 10;
}
while (i > 0){
if (n >= i){
int m = n / i;
if (m < 4){
total += CountHelp(i) * m;
n -= i * m;
}
else if (m == 4){
total += CountHelp(i) * 4 + n - 4 * i + 1;
break;
}
else{
total += CountHelp(i) * (m - 1) + i;
n -= i *m;
}
}
i /= 10;
}
return total;
}
int Count2(int n)
{
int total{ 0 };
for (int i = 1; i <= n; ++i){
string s = to_string(i);
if (s.find("4") != string::npos){
total++;
}
}
return total;
}
int main()
{
cout << sizeof(char) << endl;
for (int i = 1; i <= 10001; ++i){
cout << setw(5) << i << " -- " << i - Count(i) << "" << endl;
}
cout << "The end" << endl;
return 0;
}
Output
9494 -- 6155
9495 -- 6155
9496 -- 6155
9497 -- 6155
9498 -- 6155
9499 -- 6155
9500 -- 6156
9501 -- 6157
9502 -- 6158
9503 -- 6159
9504 -- 6159
9505 -- 6160
9506 -- 6161
9507 -- 6162
9508 -- 6163
9509 -- 6164
9510 -- 6165
9511 -- 6166
9512 -- 6167
9513 -- 6168
9514 -- 6168
9515 -- 6169
9516 -- 6170
9517 -- 6171
9518 -- 6172
9519 -- 6173
9520 -- 6174
9521 -- 6175
9522 -- 6176
9523 -- 6177
9524 -- 6177
9525 -- 6178
9526 -- 6179
9527 -- 6180
9528 -- 6181
9529 -- 6182
9530 -- 6183
9531 -- 6184
9532 -- 6185
9533 -- 6186
9534 -- 6186
9535 -- 6187
9536 -- 6188
9537 -- 6189
9538 -- 6190
9539 -- 6191
9540 -- 6191
9541 -- 6191
9542 -- 6191
9543 -- 6191
9544 -- 6191
9545 -- 6191
9546 -- 6191
9547 -- 6191
9548 -- 6191
9549 -- 6191
9550 -- 6192
9551 -- 6193
9552 -- 6194
9553 -- 6195
9554 -- 6195
9555 -- 6196
9556 -- 6197
9557 -- 6198
9558 -- 6199
9559 -- 6200
9560 -- 6201
9561 -- 6202
9562 -- 6203
9563 -- 6204
9564 -- 6204
9565 -- 6205
9566 -- 6206
9567 -- 6207
9568 -- 6208
9569 -- 6209
9570 -- 6210
9571 -- 6211
9572 -- 6212
9573 -- 6213
9574 -- 6213
9575 -- 6214
9576 -- 6215
9577 -- 6216
9578 -- 6217
9579 -- 6218
9580 -- 6219
9581 -- 6220
9582 -- 6221
9583 -- 6222
9584 -- 6222
9585 -- 6223
9586 -- 6224
9587 -- 6225
9588 -- 6226
9589 -- 6227
9590 -- 6228
9591 -- 6229
9592 -- 6230
9593 -- 6231
9594 -- 6231
9595 -- 6232
9596 -- 6233
9597 -- 6234
9598 -- 6235
9599 -- 6236
9600 -- 6237
9601 -- 6238
9602 -- 6239
9603 -- 6240
9604 -- 6240
9605 -- 6241
9606 -- 6242
9607 -- 6243
9608 -- 6244
9609 -- 6245
9610 -- 6246
9611 -- 6247
9612 -- 6248
9613 -- 6249
9614 -- 6249
9615 -- 6250
9616 -- 6251
9617 -- 6252
9618 -- 6253
9619 -- 6254
9620 -- 6255
9621 -- 6256
9622 -- 6257
9623 -- 6258
9624 -- 6258
9625 -- 6259
9626 -- 6260
9627 -- 6261
9628 -- 6262
9629 -- 6263
9630 -- 6264
9631 -- 6265
9632 -- 6266
9633 -- 6267
9634 -- 6267
9635 -- 6268
9636 -- 6269
9637 -- 6270
9638 -- 6271
9639 -- 6272
9640 -- 6272
9641 -- 6272
9642 -- 6272
9643 -- 6272
9644 -- 6272
9645 -- 6272
9646 -- 6272
9647 -- 6272
9648 -- 6272
9649 -- 6272
9650 -- 6273
9651 -- 6274
9652 -- 6275
9653 -- 6276
9654 -- 6276
9655 -- 6277
9656 -- 6278
9657 -- 6279
9658 -- 6280
9659 -- 6281
9660 -- 6282
9661 -- 6283
9662 -- 6284
9663 -- 6285
9664 -- 6285
9665 -- 6286
9666 -- 6287
9667 -- 6288
9668 -- 6289
9669 -- 6290
9670 -- 6291
9671 -- 6292
9672 -- 6293
9673 -- 6294
9674 -- 6294
9675 -- 6295
9676 -- 6296
9677 -- 6297
9678 -- 6298
9679 -- 6299
9680 -- 6300
9681 -- 6301
9682 -- 6302
9683 -- 6303
9684 -- 6303
9685 -- 6304
9686 -- 6305
9687 -- 6306
9688 -- 6307
9689 -- 6308
9690 -- 6309
9691 -- 6310
9692 -- 6311
9693 -- 6312
9694 -- 6312
9695 -- 6313
9696 -- 6314
9697 -- 6315
9698 -- 6316
9699 -- 6317
9700 -- 6318
9701 -- 6319
9702 -- 6320
9703 -- 6321
9704 -- 6321
9705 -- 6322
9706 -- 6323
9707 -- 6324
9708 -- 6325
9709 -- 6326
9710 -- 6327
9711 -- 6328
9712 -- 6329
9713 -- 6330
9714 -- 6330
9715 -- 6331
9716 -- 6332
9717 -- 6333
9718 -- 6334
9719 -- 6335
9720 -- 6336
9721 -- 6337
9722 -- 6338
9723 -- 6339
9724 -- 6339
9725 -- 6340
9726 -- 6341
9727 -- 6342
9728 -- 6343
9729 -- 6344
9730 -- 6345
9731 -- 6346
9732 -- 6347
9733 -- 6348
9734 -- 6348
9735 -- 6349
9736 -- 6350
9737 -- 6351
9738 -- 6352
9739 -- 6353
9740 -- 6353
9741 -- 6353
9742 -- 6353
9743 -- 6353
9744 -- 6353
9745 -- 6353
9746 -- 6353
9747 -- 6353
9748 -- 6353
9749 -- 6353
9750 -- 6354
9751 -- 6355
9752 -- 6356
9753 -- 6357
9754 -- 6357
9755 -- 6358
9756 -- 6359
9757 -- 6360
9758 -- 6361
9759 -- 6362
9760 -- 6363
9761 -- 6364
9762 -- 6365
9763 -- 6366
9764 -- 6366
9765 -- 6367
9766 -- 6368
9767 -- 6369
9768 -- 6370
9769 -- 6371
9770 -- 6372
9771 -- 6373
9772 -- 6374
9773 -- 6375
9774 -- 6375
9775 -- 6376
9776 -- 6377
9777 -- 6378
9778 -- 6379
9779 -- 6380
9780 -- 6381
9781 -- 6382
9782 -- 6383
9783 -- 6384
9784 -- 6384
9785 -- 6385
9786 -- 6386
9787 -- 6387
9788 -- 6388
9789 -- 6389
9790 -- 6390
9791 -- 6391
9792 -- 6392
9793 -- 6393
9794 -- 6393
9795 -- 6394
9796 -- 6395
9797 -- 6396
9798 -- 6397
9799 -- 6398
9800 -- 6399
9801 -- 6400
9802 -- 6401
9803 -- 6402
9804 -- 6402
9805 -- 6403
9806 -- 6404
9807 -- 6405
9808 -- 6406
9809 -- 6407
9810 -- 6408
9811 -- 6409
9812 -- 6410
9813 -- 6411
9814 -- 6411
9815 -- 6412
9816 -- 6413
9817 -- 6414
9818 -- 6415
9819 -- 6416
9820 -- 6417
9821 -- 6418
9822 -- 6419
9823 -- 6420
9824 -- 6420
9825 -- 6421
9826 -- 6422
9827 -- 6423
9828 -- 6424
9829 -- 6425
9830 -- 6426
9831 -- 6427
9832 -- 6428
9833 -- 6429
9834 -- 6429
9835 -- 6430
9836 -- 6431
9837 -- 6432
9838 -- 6433
9839 -- 6434
9840 -- 6434
9841 -- 6434
9842 -- 6434
9843 -- 6434
9844 -- 6434
9845 -- 6434
9846 -- 6434
9847 -- 6434
9848 -- 6434
9849 -- 6434
9850 -- 6435
9851 -- 6436
9852 -- 6437
9853 -- 6438
9854 -- 6438
9855 -- 6439
9856 -- 6440
9857 -- 6441
9858 -- 6442
9859 -- 6443
9860 -- 6444
9861 -- 6445
9862 -- 6446
9863 -- 6447
9864 -- 6447
9865 -- 6448
9866 -- 6449
9867 -- 6450
9868 -- 6451
9869 -- 6452
9870 -- 6453
9871 -- 6454
9872 -- 6455
9873 -- 6456
9874 -- 6456
9875 -- 6457
9876 -- 6458
9877 -- 6459
9878 -- 6460
9879 -- 6461
9880 -- 6462
9881 -- 6463
9882 -- 6464
9883 -- 6465
9884 -- 6465
9885 -- 6466
9886 -- 6467
9887 -- 6468
9888 -- 6469
9889 -- 6470
9890 -- 6471
9891 -- 6472
9892 -- 6473
9893 -- 6474
9894 -- 6474
9895 -- 6475
9896 -- 6476
9897 -- 6477
9898 -- 6478
9899 -- 6479
9900 -- 6480
9901 -- 6481
9902 -- 6482
9903 -- 6483
9904 -- 6483
9905 -- 6484
9906 -- 6485
9907 -- 6486
9908 -- 6487
9909 -- 6488
9910 -- 6489
9911 -- 6490
9912 -- 6491
9913 -- 6492
9914 -- 6492
9915 -- 6493
9916 -- 6494
9917 -- 6495
9918 -- 6496
9919 -- 6497
9920 -- 6498
9921 -- 6499
9922 -- 6500
9923 -- 6501
9924 -- 6501
9925 -- 6502
9926 -- 6503
9927 -- 6504
9928 -- 6505
9929 -- 6506
9930 -- 6507
9931 -- 6508
9932 -- 6509
9933 -- 6510
9934 -- 6510
9935 -- 6511
9936 -- 6512
9937 -- 6513
9938 -- 6514
9939 -- 6515
9940 -- 6515
9941 -- 6515
9942 -- 6515
9943 -- 6515
9944 -- 6515
9945 -- 6515
9946 -- 6515
9947 -- 6515
9948 -- 6515
9949 -- 6515
9950 -- 6516
9951 -- 6517
9952 -- 6518
9953 -- 6519
9954 -- 6519
9955 -- 6520
9956 -- 6521
9957 -- 6522
9958 -- 6523
9959 -- 6524
9960 -- 6525
9961 -- 6526
9962 -- 6527
9963 -- 6528
9964 -- 6528
9965 -- 6529
9966 -- 6530
9967 -- 6531
9968 -- 6532
9969 -- 6533
9970 -- 6534
9971 -- 6535
9972 -- 6536
9973 -- 6537
9974 -- 6537
9975 -- 6538
9976 -- 6539
9977 -- 6540
9978 -- 6541
9979 -- 6542
9980 -- 6543
9981 -- 6544
9982 -- 6545
9983 -- 6546
9984 -- 6546
9985 -- 6547
9986 -- 6548
9987 -- 6549
9988 -- 6550
9989 -- 6551
9990 -- 6552
9991 -- 6553
9992 -- 6554
9993 -- 6555
9994 -- 6555
9995 -- 6556
9996 -- 6557
9997 -- 6558
9998 -- 6559
9999 -- 6560
10000 -- 6561
10001 -- 6562
The end
Press any key to continue . . .