For the problems, see tutorial document 1.3.
The implementation by Harry Rowan, given below, optimally solves the problem in O(n) time:
def dictfunc(x,y):
q1,q2,q3 = 0,0,0
mydict = {}
for i in x:
if i%10 == y:
q1 += 1
if i%10 not in mydict:
mydict.update({i%10:1})
else:
mydict[i%10] += 1
mykeys = list(mydict.keys())
myvalues = list(mydict.values())
for i in range(len(mykeys)):
for j in range(len(mykeys)):
if (mykeys[i]*mykeys[j])%10 == y:
if i == j:
q2 += myvalues[i]*(myvalues[i]-1)
else:
q2 += myvalues[i]*myvalues[j]
for k in range(len(mykeys)):
if(mykeys[i]*mykeys[j]*mykeys[k])%10 == y:
if i == j and i == k:
q3 += myvalues[i]*(myvalues[i]-1)*(myvalues[i]-2)
elif i == j:
q3 += myvalues[i]*(myvalues[i]-1)*myvalues[k]
elif i == k:
q3 += myvalues[i]*myvalues[j]*(myvalues[i]-1)
elif j == k:
q3 += myvalues[i]*myvalues[j]*(myvalues[j]-1)
else:
q3 += myvalues[i]*myvalues[j]*myvalues[k]
return [q1,q2,q3]
Among the submitted solutions, there was one (also by Harry Rowan) that improved the performance of the function solving the number matching problem. For this purpose, the follwing code was suggested:
def sum2(x, y):
mydict = {}
for i in range(len(x)):
c = y - x[i]
if c in mydict:
return [c, x[i]]
mydict[x[i]] = i
return []
The exact outcome for the fraction of cases with a match would have been 1 - e -1/2 = 0.393469... The submitted numerical estimates for this fraction did not turn out to be any more accurate than the estimate that had already been provided in the problem statement ("about 39% to 40%").