0

Problem

Given a list of integers, identify sequences where successive numbers exactly N indexes apart have a value equal to N multiplied by the previous number in the sequence.

Rules:

  • N must be greater than 1

  • Sequences with less than 3 entries should be ignored

  • Sequences returned must always be the longest possible for a given value of N

  • Sequences of all zeros do not count

My Solution

  1. Iterate the list of numbers of length M

  2. At each iteration:

    1.a hold the current number and current index in current_number and current_index respectively.

    1.b Calculate the maximum possible number of successive number sequences the current_number can fit in, and hold this number in nested_iteration_count.

    1.c Start the nested iteration with a loop count of nested_iteration_count and N at the minimum possible value of N = 2

    1.c.1 Check if a sequence exists. If it exists, store the sequence in an array

    1.c.2 Increment N by 1 and repeat the loop until the inner loop iterations are complete.

  3. Repeat outer loop for next number

Example

Consider the following list of integers:

Number 2 10 4 3 8 6 9 9 18 27

Index 0 1 2 3 4 5 6 7 8 9

The following sequences are found:

  • 2, 4, 8
  • 3, 9, 27

This algorithm obviously has O(n^2) complexity. Is it possible to improve on this?

Priyath Gregory
  • 927
  • 1
  • 11
  • 37
  • 4
    Problem formulation seems not very clear. Could you show an example? – MBo Nov 07 '18 at 07:55
  • you may use the fact that for a given element of the list, the sequence elements for different values of `N` would coincide, for example, index of a sequence element number 4 for start element `arr[0]` and `N=2` is the same as index of a sequence element number 3 for start element `arr[0]` and `N=3`. but their values cannot be the same because `arr[0] * 2 * 2 * 2` is not equal to `arr[0] * 3 * 3`. hence if you find a qualifying sequence for `N=2`, you may surely skip inspecting `N=3` – mangusta Nov 07 '18 at 08:18
  • 1
    All possible sequences for N=2 can be checked in O(M) time, where M is the length of the input list. In fact, all sequences for any particular N can be checked in O(M) time. So the question becomes: "How many values of N do you need to check?" One answer is that you need to check every N up to M/2. But the other answer is that you need to check every N such that `a*N*N <= b`. In other words, `N <= sqrt(b/a)` where `b` is the largest value in the list, and `a` is the smallest. – user3386109 Nov 07 '18 at 08:57
  • @MBo I have updated the question with an example – Priyath Gregory Nov 07 '18 at 09:21
  • 1
    Yes, thanks. So you need to retrieve geometric progressions on subsequences with predefined steps. – MBo Nov 07 '18 at 09:23
  • @user3386109 interesting observation, could you elaborate why do you think it is sqrt (b/a), not just b/a? – mangusta Nov 07 '18 at 09:35
  • 1
    because N is squared in formula for minimal length 3: `a*N*N <= b` – MBo Nov 07 '18 at 09:38
  • so why is it squared i.e. why do you think it is `a*N*N<=b`, not `a*N<=b`? – mangusta Nov 07 '18 at 09:52
  • 2
    geometric progression with 3 members: `a, a*N, a*N*N` – MBo Nov 07 '18 at 09:54
  • right, the sequence should have at least 3 elements, that ran out of my attention – mangusta Nov 07 '18 at 09:56
  • @user3386109 would it be correct to assume the complexity of this solution would be O(M) * O(sqrt(b/a)) – Priyath Gregory Nov 07 '18 at 13:05
  • @fsociety Looks like I missed all the fun, but MBo seems to have covered it pretty well. Here's something new to consider. Obviously, the ratio `b/a` only applies if `b` is after `a` in the array, and at a certain distance from `a`. So you could find the largest value that follows each element of the array, and use that information to compute the worst case ratio `b/a`. Similar (but not identical) to [this question](https://stackoverflow.com/questions/24103061). – user3386109 Nov 07 '18 at 20:07

1 Answers1

2

Quick-made Python implementation using @user3386109 optimization

The first stage checks whether progression with multiplier N is continued with i-th item

The second stage - retrieving of the longest sequence for every N - might be made more concise

res contains the longest progressions for (N:(count, endingindex) {2: (3, 4), 3: (3, 9)}

import math
lst = [2,10,4,3,8,6,9,9,18,27]
l = len(lst)
mp = {}
mn = min(lst)
mx = max(lst)
nmax = int(math.sqrt(mx / mn))
for i in range(2, l):
    for n in range(2, min(i, (l - 1)//2, nmax) + 1):
        if lst[i - n] * n == lst[i]:
            t = (i-n, n)
            le = mp[t] if t in mp else 1
            mp[(i, n)] = le + 1

res = {}
for x in mp:
    n = x[1]
    le = mp[x]
    ending = x[0]
    if n in res:
        if res[n][0] < le:
            res[n] = (le, ending)
    else:
        res[n] = (le, ending)

print(mp)
print(res)

{(2, 2): 2, (4, 2): 3, (5, 2): 2, (6, 3): 2, (8, 2): 2, (8, 3): 2, (9, 3): 3}
{2: (3, 4), 3: (3, 9)}
MBo
  • 77,366
  • 5
  • 53
  • 86
  • 1
    This is brilliant. But the longest sequence for 3: should be (3, 9, 27). Should be a small implementation issue? I'll try and it out. Thank you! – Priyath Gregory Nov 07 '18 at 12:58
  • Also, would it be correct to assume the complexity of this solution will be would it be correct to assume the complexity of this solution would be O(M) * O(sqrt(b/a)) – Priyath Gregory Nov 07 '18 at 13:05
  • 1
    3: (3, 9) denotes sequence ending in 9-th index, so to retrieve sequence itself, one needs to extract elements at 9,6,3 indices – MBo Nov 07 '18 at 13:08
  • 2
    for very large elements `sqrt(b/a)` might be larger than length/2, so `O(M) * O(min(sqrt(b/a), M))` is better estimation – MBo Nov 07 '18 at 13:10