5
\$\begingroup\$

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]\$

\$\endgroup\$
12
  • \$\begingroup\$ Are you given a function with some number of variables an array and a third value? Also, I think the most efficient way is just brute force permutations from the array. \$\endgroup\$ Jun 12, 2018 at 22:09
  • \$\begingroup\$ @fəˈnɛtɪk brute force with early stopping for branches of values larger than k? Also, the interchangeability of a*b == b*a seems important? \$\endgroup\$
    – Seanny123
    Jun 12, 2018 at 22:14
  • \$\begingroup\$ @fəˈnɛtɪk The function is fixed. I think there might be some way to optimize this solution like two sum, but I haven't been able to figure out how yet. \$\endgroup\$ Jun 12, 2018 at 22:15
  • 1
    \$\begingroup\$ What exactly does the array contain? Floats? Integers? Positive integers? \$\endgroup\$
    – Arnauld
    Jun 12, 2018 at 23:36
  • 2
    \$\begingroup\$ Do we know if k is always an integer? it is not specified in the question. \$\endgroup\$ Jun 21, 2018 at 16:17

1 Answer 1

1
\$\begingroup\$

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).

\$\endgroup\$
4
  • \$\begingroup\$ (but I have no proof that this is the most efficient way) \$\endgroup\$ Jun 23, 2018 at 14:43
  • \$\begingroup\$ How does this determine that it isn't using the same element twice between AB/C and D/E \$\endgroup\$ Jun 24, 2018 at 14:42
  • \$\begingroup\$ @fəˈnɛtɪk That's in the isdisjoint call. And there are a lot of yet unmentioned details how it handles repeated elements: group and label the elements, i.e. replace [1,2,1,...] with [(1,0),(1,1),(2,0),...], and use the low labels for abc and (by reversing the list) the high labels for de, so if there is intersection then that combination is really not possible. \$\endgroup\$ Jun 24, 2018 at 20:02
  • \$\begingroup\$ (now changed the labels to be the indices, so in the above example we get [(1,0),(1,2),(2,1),...]) \$\endgroup\$ Jun 29, 2018 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.