11933 - Splitting Numbers

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

11933 - Splitting Numbers

Post by plamplam » Sat Jul 16, 2011 4:04 pm

Alright Im writing this post because this problem gave me quite a headache at first. The problem description is very unclear and it is hard to understand how to get the two numbers a and b from n(atleast it was difficult for me). Anyway the problem is really very easy if you understand what you have to do.
Consider the case when n = 437
N in base 2: (Converting n to binary) 110110101
The reverse binary of n is 101011011

Initially a and b will be 0.
So, reverse binary of n = 101011011
a = 000000000
b = 000000000

Whenever you see a '1' in the reverse binary of n, place a 1 in the similar position in number_a or number_b. Start with number_a first. If you store the reverse binary of n in a string then str[0] == '1' (In this example, however this is not true in all cases, the first '1' might appear in str[3], str[6], etc). So, make number_a[0] = '1'. str[1] == '0' so just continue the loop. str[2] == '1' again, so this time make number_b[2] = '1'. str[4] == '1' so this time make number_a[4] = '1'. Repeat this process until you reach NULL.

Now, char number_a and char number_b contains the binary form of a and b, but in reversed order. So I hope you know what you have to do now. You can just convert number_a and find b from the relation:
n = a + b
Good luck. :roll:
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11933 _ Splitting Numbers

Post by uDebug » Fri Feb 28, 2014 2:15 pm

Here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

25
5000
1000000
2000000000
2147483647
0
AC Output:

Code: Select all

17 8
4360 640
671808 328192
1378124800 621875200
1431655765 715827882
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11933 _ Splitting Numbers

Post by brianfry713 » Wed Jun 18, 2014 9:02 pm

Input:

Code: Select all

2147483647
1804289384
846930887
1681692778
1714636916
1957747794
424238336
719885387
1649760493
596516650
1189641422
1025202363
1350490028
783368691
1102520060
2044897764
1967513927
1365180541
1540383427
304089173
1303455737
35005212
521595369
294702568
1726956430
336465783
861021531
278722863
233665124
2145174068
468703136
1101513930
1801979803
1315634023
635723059
1369133070
1125898168
1059961394
2089018457
628175012
1656478043
1131176230
1653377374
859484422
1914544920
608413785
756898538
1734575199
1973594325
149798316
2038664371
1129566414
184803527
412776092
1424268981
1911759957
749241874
137806863
42999171
982906997
135497282
511702306
2084420926
1937477085
1827336328
572660337
1159126506
805750847
1632621730
1100661314
1433925858
1141616125
84353896
939819583
2001100546
1998898815
1548233368
610515435
1585990365
1374344044
760313751
1477171088
356426809
945117277
1889947179
1780695789
709393585
491705404
1918502652
752392755
1474612400
2053999933
1264095061
1411549677
1843993369
943947740
1984210013
855636227
1749698587
1469348095
1956297540
0
AC output:

Code: Select all

1431655765 715827882
1225327688 578961696
573112965 273817922
539527202 1142165576
571541540 1143095376
1351632962 606114832
285755648 138482688
144737289 575148098
541345865 1108414628
554306082 42210568
1112025226 77616196
336742441 688459922
271205668 1079284360
169935185 613433506
19204692 1083315368
1363288388 681609376
608256261 1359257666
1091895337 273285204
1228948033 311435394
33556497 270532676
153158993 1150296744
1180180 33825032
168970401 352624968
276859208 17843360
575291658 1151664772
269092133 67373650
574751817 286269714
8955941 269766922
77877316 155787808
714358820 1430815248
312821024 155882112
19039298 1082474632
575144585 1226835218
170021445 1145612578
77613329 558109730
1091715082 277417988
1091126568 34771600
352921634 707039760
679560209 1409458248
72360068 555814944
1110001737 546476306
1092886562 38289668
545523786 1107853588
286400770 573083652
571023624 1343521296
67274769 541139016
605309090 151589448
1159791637 574783562
612507793 1361086532
139012388 10785928
679544977 1359119394
1091649674 37916740
151076997 33726530
277369364 135406728
1145312401 278956580
558957585 1352802372
606110210 143131664
2393093 135413770
8393857 34605314
303124561 679782436
134382082 1115200
341135618 170566688
1410634794 673786132
1361643849 575833236
1218596872 608739456
538972705 33687632
1090819234 68307272
537167893 268582954
1091211394 541410336
1082688002 17973312
1146267714 287658144
1074341033 67275092
67437128 16916768
268698133 671121450
621038082 1380062464
1377862741 621036074
336070792 1212162576
541233481 69281954
343949897 1242040468
1095274788 279069256
152064645 608249106
269042960 1208128128
286557201 69869608
672206921 272910356
1344408073 545539106
1210122825 570572964
138433569 570960016
151667732 340037672
571605588 1346897064
608702993 143689762
312510608 1162101792
1378124841 675875092
152077585 1112017476
270565705 1140983972
1229459985 614533384
272706196 671241544
1376002121 608207892
576016641 279619586
541198345 1208500242
310650965 1158697130
605169924 1351127616
Check input and AC output for thousands of problems on uDebug!

Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Re: 11933 - Splitting Numbers

Post by Zyaad Jaunnoo » Sat Mar 26, 2016 11:26 pm

C++ function __builtin_ffs(x) was very handy for this problem. Used it to get the position of the least significant bit of an integer.

Post Reply

Return to “Volume 119 (11900-11999)”