Find elements in an array computing a given function value

Question

Problem Description

Given:

• a function \$f(a, b, c, d, e) = \frac{a \times b}c + \frac de\$
• an array \$x = [x_1, x_2, x_3, x_4, ..., x_n]\$ of non-distinct integers
• a target value \$k\$

What is the most efficient way, in terms of worst-case \$n\$, to find 5 distinct indices \$x_a, x_b, x_c, x_d, x_e\$ from \$x\$ such that \$f(x[x_a], x[x_b], x[x_c], x[x_d], x[x_e]) = k\$?

Example solutions

Example 1 (single solution):

\$x = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9], k = 5\$

Solution 1:

\$[1, 4, 2, 9, 3]\$ as \$f(x[1], x[4], x[2], x[9], x[3])\$ evaluates to \$5\$.

Example 2 (multiple solutions):

\$x = [0, -1, 1, -1, 0, -1, 0, 1], k = 0\$

Solution 2 (of many solutions):

\$[1, 2, 3, 5, 7]\$ OR \$[0, 1, 2, 4, 7]\$

Example 3 (no solution):

\$x = [0, -1, 1, -1, 0, -1, 0, 1], k = 8\$

Solution 3:

\$-1\$ (no solution)

Example 4 (intermediary floats):

\$x = [2, 3, 5, 4, 5, 1], k = 2\$

Solution 4:

\$[2, 3, 5, 4, 5]\$

Answer 1

Python3, O(n^3 log n)

from math import gcd
from functools import reduce

def lcm(x,y):
    return x//gcd(x,y)*y

def label(l):
    res=[(v,i) for i,v in enumerate(l)]
    res.sort()
    return res

def sortcombine(l):
    l.sort()
    res=[]
    oldval=None
    for val,how in l:
        if val==oldval:
            res[-1][1].append(how)
        else:
            oldval=val
            res.append((val,[how]))
    return res

def getabc(L,xl):
    N=len(xl)
    res=[]
    lasta=None
    for ai in range(N):
        a,al=xl[ai]
        if a==lasta:
            continue
        lasta=a
        lastb=None
        for bi in range(ai+1,N):
            b,bl=xl[bi]
            if b==lastb:
                continue
            lastb=b
            lastc=None
            for c,cl in xl:
                if c in [0,lastc] or cl in [al,bl]:
                    continue
                lastc=c
                res.append((L//c*a*b,(al,bl,cl)))
    return sortcombine(res)

def getde(L,xl):
    res=[]
    xl.reverse()
    lastd=None
    for d,dl in xl:
        if lastd==d:
            continue
        lastd=d
        laste=None
        for e,el in xl:
            if e in [0,laste] or el==dl:
                continue
            laste=e
            res.append((L//e*d,(dl,el)))
    return sortcombine(res)

def solve(l,k):
    xl=label(l)
    L=reduce(lcm,[v for v in l if v!=0],1)
    k*=L
    abc=getabc(L,xl)
    de=getde(L,xl)
    i=0
    j=len(de)-1
    while i<len(abc) and j>=0:
        v1,ls1=abc[i]
        v2,ls2=de[j]
        s=v1+v2
        if s==k:
            for l1 in ls1:
                s=set(l1)
                for l2 in ls2:
                    if s.isdisjoint(l2):
                        return list(l1+l2)
            i+=1
            j-=1
        elif s<k:
            i+=1
        else:
            j-=1
    return None

Try it online!

Multiply the equation by the LCM of the x values to avoid floating point or fractions. Find all possible values of ab/c (using ab=ba but that's only for a factor of 1/2) and d/e, sort them and try to add them to the wanted result. The sorting means we don't have to try all combinations.

There are O(n^3) possible values for ab/c, sorting them gives the log. The other steps are faster than that.

The while loop may be repeated O(n^3) times, but the case s==k can only occur O(n^2) times. If we don't find a solution and stop in this case, then the sizes of ls1 and ls2 (number of ways to obtain the corresponding value) must be in O(n) resp. O(1) (except in the case when the value is 0, but luckily that doesn't happen O(n) times).