1
$\begingroup$

Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.

More precisely, given a triplet $(i,j,k)$ with $i<j<k,$ it satisfies the question above if $A[i] \times A[j] \times A[k] = target$ and either ($j = i+1$ and $k > j+1$) or ($k = j+1$ and $i < j -1$.)

For example, if the list given is $A = [1,2,2,2,4]$ and target $= 8,$ then the answer is $2$ as $(0, 1, 4)$ and $(0, 3, 4)$ are the only triplets satisfying conditions above if we use $0$-based numbering.

I stucked at this question for 3 hours and not able to solve it.

Any hint is appreciated.

$\endgroup$
2
  • $\begingroup$ What does "two of the triplets must be adjacent"? $\endgroup$
    – gnasher729
    May 20 '20 at 12:50
  • $\begingroup$ @gnasher729 I edited the question. Hopefully it is clearer now. $\endgroup$
    – Idonknow
    May 20 '20 at 12:59
1
$\begingroup$

This will run fast unless someone creates a list specifically to make it hard for you:

Set count to 0.
Create a hash map with duplicates of all integers dividing the target, with their positions. 
For all adjacent pairs i, i+1
  If A[i] * A[i+1] divides the target
    Look up all x equal to target / (A[i] * A[i+1])
    For each x
      If position < i-1 or position > i+2
        Increase count by 1.

This will be fast, assuming most products don't divide target.

$\endgroup$
1
  • $\begingroup$ This is nice and what I am looking for. Thanks. $\endgroup$
    – Idonknow
    May 21 '20 at 0:21
1
$\begingroup$

Let $n$ be the number of integers and $t$ be the target integer. You can solve your problem in $O(n \log n)$ time as follows:

For every $i=0, \dots, n-1$, let $p = A[i] \cdot A[i+1]$ and compute, in $O(\log n)$ time, the number $\eta(t/p)$ of integers in $A$ that are equal to $t/p$ (more on that later). Then the number $\gamma_i$ of triplets formed by $A[i]$, $A[i+1]$ and a non-adjacent element is $\gamma_i = \eta(t/p) - |\{A[j]=t/p \, : \, i-1 \le j \le i+2 \}|$.

It follows that the number of triplets of interest is $\sum_{i=1}^{n-1} \gamma_i$.

To find the values $\eta(\cdot)$ do a preprocessing in which you create a copy $B$ of $A$, sort $B$ in $O(n \log n)$ time, and append an element with value $+\infty$ to $B$ (this is just to avoid edge cases, $+\infty$ can actually be any integer greater than $t$).

If $x \not\in\mathbb{Z}$, $\eta(x)=0$. Otherwise $\eta(x)$ can be found in $O(\log n)$ time by binary searching for the smallest indices $i$ and $j$ in $B$ such that $B[i]\ge x$ and $B[j] > x$, respectively. Notice that $i$ and $j$ are always well defined and that $\eta(x) = j-i$.

$\endgroup$
6
  • $\begingroup$ Given a triplet $(i,j,k)$ with $i<j<k,$ there are 3 possibilities: $(1)$ All three are together (i.e. $j = i+1$ and $k = i + 2$); $(2)$ Exactly two are adjacent and the remaining is not adjacent or $(3)$ All three are separated (i.e. $i < j - 1 $ and $j < k -1$). Am I right? $\endgroup$
    – Idonknow
    May 20 '20 at 12:15
  • $\begingroup$ Yes. But in your problem statement you don't want to count triples of the third kind. $\endgroup$
    – Steven
    May 20 '20 at 12:23
  • $\begingroup$ May I know the purpose of computing the number of triplets in which all three elements are adjacent? Initially I thought you want to use complement method to calculate triples of second kind. However, it seems that you are not doing so. $\endgroup$
    – Idonknow
    May 20 '20 at 12:26
  • $\begingroup$ The rest of the algorithm only works for computing the number $\gamma$ of triplets of the second kind, so we need to add the number of triplets of the first kind to $\gamma$. $\endgroup$
    – Steven
    May 20 '20 at 12:30
  • $\begingroup$ Your edited question now excludes triplets of the first kind... (they were included previously since a triplet of the first kind also has two adjacent elements). Can you confirm that you are only interested in the triplets of the second kind? If so I'll update my answer. $\endgroup$
    – Steven
    May 20 '20 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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