CODEWITHSUNDEEP
javascriptarraysalgorithmmatharray-algorithms
Daniel Marques
Daniel Marques

Reputation: 526

Get the most number of strictly evenly spaced elements of an array up to 'N'

I want to get N elements from an array, such that the elements are evenly spaced between each other. As a restriction, I also want the first and last elements to always be picked.

Other edge cases include:

After looking around I came across several answers that solved this problem (e.g., here and here). And they work, but I realized I had more constraints that weren't addressed.

The answers presented are loose in the sense that if they're off-by-one, then it wouldn't be a big deal. In my case, it is, thus the term strict in the title.

For example, given L=6 and N=3, in loose form:
A = [ 0, 1, 2, 3, 4, 5 ]
R = [ 0, 2, 5 ] or R = [ 0, 3, 5 ]

However, neither results are strictly evenly spaced as for L=6,N=3 such result is simply not possible.

What I am looking for is to loose the N variable. In other words, to decrement N to the closest number which makes the problem possible.
In the case of L=6,N=3, that number would be N=2 which would result in R = [ 0, 5 ].

I could do a trial-and-error solution with the answers from the previously mentioned answers (simply testing and decrementing N by 1), but I'm trying to think of a more performant solution.

Last remark: I'm looking for ideas, and thus pseudo-code is completely fine! I am, however, going to implement it in Javascript, so please don't rely on other language-specific functionality.

Edit: The actual array elements might not be numbers (and there are no order guarantees).

Upvotes: 1

Views: 644

Answers (1)

RaffleBuffle
RaffleBuffle

Reputation: 5455

For a given Length the valid values of N are equal to fac+1, where fac is a factor of Length-1.

First consider the edges cases: 1 and Length-1 are obviously factors, which gives N=2 and N=Length.

If Length-1 is prime then these are the only options, as is the case with Length=6 in the example you gave.

For Length=7, {0, 1, 2, 3, 4, 5, 7}, factors are (1,2,3,6), so options are N=2,3,4,7:

{0, 7}
{0, 3, 7}
{0, 2, 4, 7}
{0, 1, 2, 3 4, 5, 7}

So, for a given Length and N, determine the largest value M such that M <= N and M-1 is a factor of Length-1. Something like this (Java) would work:

static int maxN(final int len, final int n)
{
    int maxN = n;
    while((len-1) % (maxN-1) != 0) 
        maxN -= 1;
    return maxN;
}

There may be more efficient approaches.

Upvotes: 1

Related Questions