Multiply me out!

Computer Science Level 4

Given below is a number with 10 , 000 10,000 digits. Find the fourteen adjacent digits in this number that have the greatest product. What is the value of this product? 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
 
54751370984417811334303799117222265665364310835907
34023206130455409008408119067410245664755180133057
86148705278840618915781106630715629430284980715094
48548585762064487039006963094970954900718450209740
09153109398338228434617466337196532207890503112577
06500027404992565508131859424761369342508948908187
12630002744203092166284021367675527763680525574772
26702731595205610944272469437631425820182902574699
76330018982283603587718239407828135900809218759336
82823474178144036993599488201100782089460080009108
61497549692990392950862821037567199622326590014900
72684380073694434852930154168074495357246011186448
76781287618881082636925077864468053324005387998942
16698137091468067218924667774656758242742483688364
17891874715519126367756972763778128462203830165964
12900346341366924579389141466703225454672818594816
83620796449333097688469007556969944677060459626329
35216945024204437834339937960072817641816473836056
39325681372974648298143937106200516830253532427476
30308590413510148770705557653576919473568397132161
47777709246402337803640445299547583420709151357660
32512672806736431875008374948599816547921808762935
96012155670820406955452747884347955798645779416547
20364563788694941555993765339540423736760889417150
53728656841196580332211427380714293641542121807617
61331811163714470270876412174036825954564715043668
63822624538087493204090880562331734144532992167695
87923162765369680443317930165133597006154049422176
02647482652243980884530678221519495806280253780483
78253439228343718314660508489140367577706846126117
45535138002156411495768513202637082761310152847774
74994267941741601667695049682870789869667729890886
36943069377813774384450531017507742468043533062787
75038306518585101985659295906213406589738533142051
97844756361349917659522710396746158717949103448209
77484679206668793082411708582241010492354770080159
96085995489139200725255430003687689181125213387430
25205349062770581293195370443032322404565850058593
26583690422070363849134219835640477278551591430790
32937851000605262588070415469136090786021456700304
90242214951299498073639377180336256189332521606699
61656714311421812666198720726147785569497145104027
39282892262929407011479403968716977995102453459759
38362067225317985672954134006993488877000311542597
88202820847290982265490938912568712799726576859607
90194748378333787786364499462629378465034008722985
38238810568184468199676318193757544935331141418098
91935468783120443509421367023011039940321020045498
27878463402803974513789731975176339267102044499773
06950376264106007362762171390315897066045159209156
56050898074854370994384726517708305116894414820038
45758269497701902028110036267302636597875332357445
80780009390692970886022821528530715247012481169106
35138241589419136734108490311477640015200769159871
02997039829006237050110904944392204761507210579333
77123240398739875040632834419390233596414740828593
31699405528312820384069492648562055476932234203389
70749908727087261253077698693603904054123669261287
59914149694156282724277833039615072457433571180407
97600619087352148628789678452127720820548003066769
75015149768449589411999952858375282218803723521255
75358839945768589407609479627116138056228362655231
94213310165131075563646268219786658173129185279257
91825910907277431690779155909833921118054903826690
67313961885718967843401099920322424409996042591890
92906900329016344232095795691600001860679425813638
88010577521202172571729592439304807120414147699218
50061555311291953957498503325904186010275911400035
82680770727317753958713595016624486764689614025468
91701566481706588337905705000049318408372848516555
83328048985151107264740435194611573874785323965763
36866879681666760182534977749684274447964070521663
22905164626402134745039558919092372953843196054034
20857887871974404898549328164695625009530268992255
38704636677191835822103496283812343685163716450304
27251374326494035484603294847808924993912580165822
74299993892565312622378217745422992353849918582216
07951341414190316046277706845310142612411582206764
26905404164910015351184695794039826741162378217261
52897012332439761666540055244783196763688677941936
38070609024942729785540438329207641451221493010431
87328351319208819372267551693756779207614608204445
68202814568586681702016735815806845535282376489940
15729100635616875779432542006243784907285842457289
92972189113701860918457435010257053206414620313765
07202459788141040248873185963245629037821030199151
35042123334526226285338670732136266496309209258397
05718602150221917863198514392876332105435979801150
30485517119928532270623426491764907684866891973966
35981226065016324325266340347740827656134787474330
83096661492185581985019615038471411740829328650487
13387422775159182085468478523889625432251207542954
01654249757100375898045200119768336069957329076559
99483426524863060784492830774485410765829763458912
73663206676519649484676803599345487106155680411280
10079933433044957516519081218587872449686574501112
45283862633022384931998529365339988116996109010927
97655726381600262870923625854682268181883963411486
89403833328923206496927142540240323118058106386302
04592689699194597843951329858314787762511877601288
81853922268067750445341571595045722990295270720745
86132569863585063850377578924886015186085140065348
10827896078162334125550590426499867721791633163996
63245846023402314911903570092145020822471915233192
87456701563589585743049934131572180276101419689086
47640957955890872177478637676967587925321974071162
07943203973157300239173848136728696915376365851091
41861294131573546854183605803479230008411348717841
16561759595184029384074716492086988505572702764040
82459755496046790556190367576614824089902998435656
39977792405197881775025991925134447572105753331887
34871628406377134055388146127854246320656674268198
03860750425775204593562795836126776129857413944701
80603582974799483797865550362942514403051163414574
92314568319493964804668518544638031947474772338967
66381102358445801207773885272408644996927519735975
91425972546854488743161013983120489698897314027674
24723311171845378871104488623559043280282445398460
59522225786518252069641079465215061584095159496183
98799641316964390727724907807620092482346637354100
06428538005476542964327489286599842394706533790503
43983156660636725705739411106252606075611426076519
45532170762892294095616262533265097259812843013519
38487196625574407755467969995471881869207431957683
70218764555246001066850119687264634407447811649626
50046946071999896143717259340339510013295840687592
06051482323174178290822362176159723318822567927778
88709306302425288332566306721966883584874553023947
51601716168255023248388061206077087332941333311443
05262625908259330651543744114867633963101883573509
49077077345053447854272296596668242987062188609676
98004440339248975279971924271338653885108140825866
55358219026323398575457658647617007921331880954466
57042802477789965145147343893475832415460970303794
03744850951235484841532808378846836337551402952937
18337099300545916913689008416689329541229101376754
69430888168511792129251275836129336955900439921880
90053918179059346944381800751581414898710265288087
38084215911671980147888024435258996095467707310855
14686030129470709428740430328605618162211741115749
31255025145860515766937840214423089158144634871491
49764842929675924456297603414254846203542684385759
17884276686787213816823298159620572061979969470510
30034250172614473726496558205809217295411282987084
06829398068256481202298983740804203238109869551877
73199562320886440775806815187489502172427840972759
37721716352942798983280283850280000812703603009638
00340555358854310622654463981815573590410744004536
36355359920108364041545487820932506142959101431272
17443606295618077545214774595598006850669009711587
22170448981841020253225169357891442569950714965397
57982213610349367521678785146785932910240299570087
58265161269413034668981673217822085672788625642970
30768986327142948689882700097492911356267899625632
51071490414271256814231119892345501300982321669448
41924572691004713504521039072214662166417210751133
52562856873361410386978782885593179738137439658055
87513799748013934673145324232738652046306477358557
54523605091855475451434483272303127589289381809950
16759987372812766820422424608804619235030051782373
04083900870132662432781871435328195406313844674199
56522417077958147021403375667085574545859031658097
61023577793003695243822011065902386605078645460552
34635812151553570945658202858591469184015795412963
18027352904290415353943442062969888642757081856400
00252404225418288362655238275393016587930395486097
24722531208291420239460541963146419874297391393763
67291242883494229606313962115436377550717244865694
72935325584869686144865430884326508876741451317664
50802230151849590804573769479035306185279297912235
14567312213476280123554350248813663294768934948250
49313456966096249713433298937211586757026673446186
75372295963644643462507038290818590616055756888561
60807428193167173267496586243922134379955964357810
48742101849804800397183772032926608227970241039383
56550229631949850199107743780586743885483825865219
46526098852215893830893641968934129339551128891418
39781204449751481318902744898616713836066832913300
02235066967375229268520379588639114479794680193908
62923057793666721708126863794622393721734278198847
66815750317289852805481571501438630108332021095524
50128888419187584118307111795004703417250493099998
38173736404834823903214575948333430821077741319412
02458359747506522247480781207755715229653721465871
82780922160326190911903154834987908392820165379617
54284166459672894494197957226473666147406094589453
46702279886321978594901034890650994720750535985741
82630339619082861074078269580077164815962961724495
40269418416700484668862475608448897320083298566664
40370642913525872453529626986706988678191110746816
60746394638129702020447883160945801693867265496824
70081849916729207251225040279663848415908440901074
41904508297470199625746002408998840650764461682574
08885314121707469741432348184507128183404226293762
01549893110099301718256529992529648486071904553649
80909407649431419787301764587141043085448009605176
36063827725626887670777579924479918983946133483420
01045891299316776971021396263357285610412338300786
77052262390943799177027954503408882863792862493090
10019131454352321510529032694454174750880034327604


The answer is 497757560832.

View wiki
Raghav Vaidyanathan by Raghav Vaidyanathan , 23, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions

Tarun Singh
Mar 12, 2015

Python 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
j=open('file.txt') #reading this from a text file
text=j.read()
length=len(text)
l1=[]
for i in xrange(0,length-14):
    product=1 
    for k in range(i,i+14): 
        if text[k]!='\n': 
            product=product*int(text[k]) 
    l1.append(product) 
print max(l1)

2 Helpful 0 Interesting 0 Brilliant 0 Confused

I used a circular queue to solve this problem. Please share your methods too! 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
#include<fstream.h>
#include<conio.h>

class cqueue          //circular queue implementation class
{
int cq[20],f,r,n;
public:
cqueue(int num)
    {
    n=num;
    flash();
    }
void flash()    //if any number is zero, the queue is reset
    {
    for(int i=0;i<20;cq[i]=0,i++);
    f=-1;r=-1;
    }
void push(int e)
    {
    if(f==(r+1)%n)
        pop();
    if(f==-1)
        f++;
    r=(++r)%n;
    cq[r]=e;
    }
void pop()
     {
     if(r==f)
         {
         r=-1;f=-1;
         }
     else
         {
         f=(f+1)%n;
         }
     }
void show()
    {
    if(f!=-1)
    for(int i=f;;i=(++i)%n)
        {
        cout<<cq[i]<<",";
        if(i==r)
            break;
        }
    cout<<endl;
    }
float arm()     //multiplies the numbers in the queue
    {
    float p=1;
    if(f==(r+1)%n)
    for(int i=0;i<n;i++)
        p*=cq[i];
    else
        p=0;
    return p;
    }
};

int main()
    {
    clrscr();
    char a,c='1';
    int b=c-1,j=0;
    float z=0,big=0;
    cqueue Q(14);
    ifstream iff("brilq.txt");   //number is stored here
    for(int i=0;!iff.eof();i++)
        {
        iff.get(a);
        int no=a-b;
        if(no!=0)
            Q.push(no);
        else
            Q.flash();
        z=Q.arm();
        if(z>big)
            {
            big=z;
            j=i;
            }
        }
    cout<<j<<endl<<big; //returns position of string and approximate value
    getch();
    iff.close();
    return 0;
    }

2 Helpful 0 Interesting 0 Brilliant 0 Confused

I used concentric loops to solve the problem. Check my answer for the code.

Aryan Gaikwad - 6 years, 2 months ago
Aryan Gaikwad
Mar 26, 2015

Java: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
public static void main(String args[]){
    String num = read(); //read the file containing 10000 digits
    double n = 1, lar = 0;
    for(int i = 0; i + 13 < num.length(); i++){
        for(int x = i; x < i + 14; x++)
            n *= Character.getNumericValue(num.charAt(x));
        if(n > lar) lar = n;
        n = 1;
    }
    System.out.println(lar);
}

Execution time - ~0.008 seconds

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Brock Brown
Mar 18, 2015

Python 2.7: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
number = open("number.txt").read().replace("\n","")
def product(string):
    output = 1
    for digit in string:
        output *= int(digit)
    return output
biggest = 0
length = 14
for index in xrange(len(number)-length+1):
    test = product(number[index:index+length])
    if test > biggest:
        biggest = test
print "Answer:", biggest

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
Jul 10, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
import operator

def prod(iterable):
    return reduce(operator.mul, iterable, 1)

lar = None
num = 'that large string with the 10000 digits'

for x in xrange(0, len(num) - 13):
    if prod(int(i) for i in num[x:x+14]) > lar:
        lar = prod(int(i) for i in num[x:x+14])

print lar

0 Helpful 0 Interesting 0 Brilliant 0 Confused

Moderator note:

Nice compact solution.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...