Count Nonrepetitive Numbers

Submit

Your name:
File:
Open code-statistics:

Language is selected by the extension of the file. See the list of supported languages to know the extension of your language.

Problem

Let's call an integer "repetitive" if it contains two of the same digit in a row. For example, 12232 is repetitive but 1232 is not.

Given a positive integer n < 10^15, return the number of nonrepetitive integers in [1..n].

-- mitchs

Options

exec is denied

no deadline, the server will not save your submission

Sample input:_

88367698737
8850077236345
733574391
1011
847
1766
510711296956
99
2289
240099648554
931683528699
385526433145
1033420081
8222517443
56
419529537
198861
971
5652
576
30961041
620862844455
754299627858
592833434623
70749228221
195622228062
193454
73184413688901
1000
3
1307375086571
5
101
29942926194
25295719
60113179
10198
45
407567897798
80989631
2485249
921822887790
111
11
432097147165377
9759401
52392
487463218746
924870391
7
18
2982
17812961
945052
87
705334926
985946
10
9733715
4
481690302652
255034888633807
16504
37321540589100
1474
68139091090517
859228
1520181708196
8087548
9445421307689
34934
2538178
575294384
6326294
641354426
576438358912
289754036
22
66
20818108117512
575563025514769
54334398109470
83204461689645
57414576519
244
33601530590870
646274399578
1214
67781016
27
493
76409107451
979604572051976
9244436336
323967
772
669333815319
682323652
517
333628082860
28568131
73390292130464
20
65797
884657138890507
2054240485015
67829
2440474353248
8190612
6007
991886752694
1725
9843303757667
3820
9288316085
626525633
13460160
62288784032
829100585
2926534
1
6604991
73
26245
636929
6096310183
762605416097474
94424
999
8132007
6
447565816893271
42310223853770
443922890
899377688
1912547
40727291
936858097765195
84263
4808238842
751447783587946
36868912408
2321428754841
519079248581
23993
1010
542583010008405
30
585484575
3133688888
926235
186391
8504949
9
2425949307
8
400885
2884
5173994747
68268312190899
642104682916
283794247
84
10309270
69751557
133639964
654
42
73291734542518
583123246517726
97747206866736
398565959764437
9323647245
71563272442888
378980279036
52962083
95
351416044969942
732
1009
596744
5193
36
37952
152698218464772
90662
7956
6396348
70
6782510
100
427164982739
9189190988
28
27709
2286
887510143266
49671713214
7372
21
2
923
8748696
404043126868
5884843865
280
170399801415658
837766
80134049
922613729
817
207267840
7457909075
5396225942631
110
7637
187757862
12
1378
109
507304
63430452373718
54726841096
16692
89
902167016608
5602758
433
8238144954476
49553920
331239710292
2787
226323027416632
178
944
16441246796250
7703
3095534288743
4945969883450
377083797211358
434581297714
6011
8093695948
202414
2485624
102902317667
5309793858165
86548669992
893440
1001

Sample output:

31429487169
2545788460779
322651116
820
700
1365
164578309632
90
1710
77145104871
297450506322
124625638134
447008310
3243450852
51
186916858
125397
803
4188
475
15459293
199514089152
242702793837
189814316958
25125133806
65360932137
121388
19015593055542
819
3
382980416636
5
91
10896201252
12464307
29302245
7461
41
132014202417
39392849
1356228
294025114089
99
10
102587892333370
5301703
35319
156764131539
404421095
7
17
2271
8990822
568020
80
309030480
595644
10
5284611
4
154495398819
60192794962512
11434
9739603707327
1121
17587427794225
518589
450265407559
4369436
2716640896428
23368
1390436
252143276
3449228
283472064
184263624866
129655680
20
60
5627377862703
134063809282098
14261384048139
21564045032184
20373137523
202
8790619322970
208210383369
913
32897673
25
409
27344363987
228992878836061
3637780074
199816
639
213129696510
298337961
430
108526164480
14217149
19052225815113
19
44396
206208865323189
615760253654
45153
708253081452
4429910
4464
317733228540
1328
2843456536494
2863
3659037714
276196026
6653719
22217488875
363631122
1618906
1
3609369
67
17780
385677
2414586667
178971834949565
63108
819
4391586
6
104534232190029
11116357131096
196699599
392801328
1077919
20101772
218028331998783
56434
1903293621
176096995236153
13167528578
670428749387
167447171504
16128
820
128126977708662
28
257037855
1264896009
555773
117047
4616082
9
964605121
8
243576
2187
2059400304
17628977505285
206975953023
126959281
77
5504986
33994458
59587821
545
39
19049400938996
135919656830709
25391199856131
94260988658817
3675307001
18537460042761
122081202897
26088880
87
82039452811893
606
819
360013
3892
33
25572
36656707704237
60327
5892
3489362
64
3657088
90
138814576812
3616103258
26
18882
1710
282865384530
17770221634
5493
20
2
759
4763212
130625145467
2325120804
235
41081729660631
504396
38876967
403430148
673
94818808
2955356673
1571909010813
99
5713
86041773
11
1043
99
307246
16520969835062
19690395874
11511
81
286809743763
3020147
363
2367247136742
24309324
108526164480
2105
53696915623449
152
778
4411218115314
5760
912638912760
1431944982405
88718178147093
141275801871
4465
3188001617
126463
1356457
36036147330
1545035553708
30893125419
534726
819

Ranking

Ruby _

RankUserSizeTimeDateStatistics
1mitchs780.04812017/05/24 13:37:130B / 37B / 34B

Perl _

RankUserSizeTimeDateStatistics
1tails670.01672017/05/25 15:14:180B / 19B / 48B
2mitchs690.01852017/05/24 08:50:590B / 20B / 49B

Python _

RankUserSizeTimeDateStatistics
1xsot870.03812017/05/26 15:32:560B / 46B / 30B
2mitchs880.03762017/05/20 11:21:290B / 48B / 28B

Python3 _

RankUserSizeTimeDateStatistics
1xsot870.08122017/05/26 15:34:000B / 43B / 34B
2mitchs880.07932017/05/20 11:22:410B / 45B / 32B

sed _

RankUserSizeTimeDateStatistics
1tails2340.22512017/05/22 13:46:100B / 73B / 130B

dc _

RankUserSizeTimeDateStatistics
1tails670.04672017/05/23 23:07:390B / 48B / 19B

gs2 _

RankUserSizeTimeDateStatistics
1mitchs230.32952017/05/25 04:40:4512B / 10B / 0B
2tails250.31642017/05/20 21:30:1311B / 8B / 5B

Language Ranking_

RankLangUserSizeScore
1gs2mitchs2310000
2dctails673432
3Perltails673432
4Rubymitchs782948
5Pythonxsot872643
6Python3xsot872643
7sedtails234982

return top