0
$\begingroup$

Assume we have 26 vectors ${A,B,C,....,Z}$ all have 1 million integers. given a query: $$ \vec{query} = (r_a, r_b, r_c, ..., r_c) $$ I want to find a match vector $\vec{m_{1 \times 26}} = (a, b, c, ..., z)$ that satisfies the following criterias:

$$ a \in A, b \in B, c \in C, ..., z \in Z \\ \text{and} \\ r_{a} = \frac{a}{\sum_{\theta \in m}{\theta}}, r_{b} = \frac{b}{\sum_{\theta \in m}{\theta}}, ..., r_{z} = \frac{z}{\sum_{\theta \in m}{\theta}} $$ in which $\sum_{\theta \in m}{\theta}$ is basically sum of the values in vector m. In other words, let say given the amount of share each $a, b, c, ..., z$ has in my math vector m, I want to find the elements. Of course, one yet not feasible solution is checking all ${(10^6)^{26}}$ possible combinations and check if there exists any match. There could be multiple answers, but any of them is fine.

Example: Let say all ${A,B,C,....,Z}$ are equal to each other and contains elements between $1$ and $10^6$ like $\{1,2,3,...,10^6\}$. given query $\vec{query} = (\frac{1}{26}, \frac{1}{26}, \frac{1}{26}, ..., \frac{1}{26})$, $m$ is one of the many possible solutions: $$ \vec{m} = (1,1,1,...,1). $$

My question is, what could be the fastest algorithm for solving this problem?

$\endgroup$
3
  • $\begingroup$ Do you really mean the query and $m$ to be a set, or do you intend them to be an ordered array/vector? $\endgroup$
    – D.W.
    May 6, 2021 at 22:41
  • $\begingroup$ How large are the integers in $A,B,\dots,Z$? Are they always in the range $[0,10^6]$ or so in your application? $\endgroup$
    – D.W.
    May 6, 2021 at 22:41
  • $\begingroup$ @D.W. Thanks for sharing your idea, its really helpful. Not sets, they're both ordered array. So I guess it is a bit misleading. And regarding the numbers, yes in $[1, 10^6]$ but could have repeating values not necessarily unique values $\endgroup$
    – aminrd
    May 7, 2021 at 15:57

1 Answer 1

1
$\begingroup$

One approach is to guess $a$ (i.e., iterate over all possibilities for it, and the following for each possibility). Then, you can infer the value of $b$, namely, $b = a r_b/r_a$, so test whether $b \in B$. Do the same for each of $c,\dots,z$. If they all work, then you have found a solution; otherwise, proceed on to your next guess at $a$. This should give you approximately a linear running time if you use the right data structures for storing the vectors (e.g., a hashtable).

A similar approach is to compute the vectors $A/r_a$, $B/r_b$, ..., $Z/r_z$, and then look for an item that occurs in all of those scaled vectors, e.g., using a hashtable or a counter or by sorting and merging the sorted lists.

$\endgroup$

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.