# Find arrays with distinct subarray sums

Consider an array A of length n. The array contains only integers in the range 1 to s. For example take s = 6, n = 5 and A = (2, 5, 6, 3, 1). Let us define g(A) as the collection of sums of all the non-empty contiguous subarrays of A. In this case g(A) = [2,5,6,3,1,7,11,9,4,13,14,10,16,15,17]. The steps to produce g(A) are as follows:

The subarrays of A are (2), (5), (6), (3), (1), (2,5), (5,6), (6,3), (3,1), (2,5,6), (5,6,3), (6,3,1),(2,5,6,3), (5,6,3,1), (2,5,6,3,1). Their respective sums are 2,5,6,3,1,7,11,9,4,13,14,10,16,15,17.

In this case all the sums are distinct.

However, if we looked at g((1,2,3,4)) then the value 3 occurs twice as a sum and so the sums are not all distinct.

For each s from 1 upwards, your code should output the largest n so that there exists an array A of length n with distinct subarray sums.

Your code should iterate up from s = 1 giving the answer for each s in turn. I will time the entire run, killing it after one minute.

Your score is the highest s you get to in that time.

In the case of a tie, the first answer wins.

Examples

The answers for s = 1..12 are n=1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9.

Testing

I will need to run your code on my ubuntu machine so please include as detailed instructions as possible for how to compile and run your code.

• s = 19 by Arnauld in C
• I am quite certain that there is no such rule. Currently there is nothing stopping anyone from just writing a simple print statement for the first 12 values that you provided and having a score of 12. It is almost certainly true that the largest value will use up most of the time, which is why I think my suggestion makes more sense. It's (of course) fine if you disagree, but I'm pretty sure you are just making your challenge much more annoying to answer for no reason. – FryAmTheEggman Nov 8 '18 at 23:21
• @FryAmTheEggman Hard-coding the output is a standard loophole. – JungHwan Min Nov 9 '18 at 1:12
• I downvoted this challenge because the nature of this challenge encourages some extent of hard-coding the solutions, and requiring the answer to "actually compute the output" is a non-observable requirement; there is no clear distinction between what is computed and what is hard-coded. – JungHwan Min Nov 9 '18 at 3:31
• @JungHwanMin Oh no! I am confused as the scoring system is basically the same as codegolf.stackexchange.com/questions/174407/… and codegolf.stackexchange.com/questions/165504/… and codegolf.stackexchange.com/questions/157049/… and... (and so on). What can I change to make you happy with my question? – Anush Nov 9 '18 at 10:45
• @JungHwanMin What's the difference between hard-coding the number 9 and hard-coding an array of length 9? It's good practice to avoid unobservable requirements whenever possible, but it's rather difficult for some kinds of challenges (fastest-code, anything related to quines, etc.). – Dennis Nov 9 '18 at 15:48

# C (gcc), s = 19

This is basically a port of my Node.js answer. It goes one step further with the default compiler options and two steps further with -O2 or -O3.

#include <stdio.h>
#include <string.h>
#include <stdint.h>

void search(uint8_t * arr, int n, uint8_t * sum, int * max, char * str, int depth) {
int i, j, k, s;
char tmp[16];

// do we have a better array?
if(depth > *max) {
for(str[0] = '\0', i = 0; i < depth; i++) {
sprintf(tmp, "%d ", arr[i]);
strcat(str, tmp);
}
*max = depth;
}

// try to append i = 1 to n to the current array
for(i = 1; i <= n; i++) {
// provided that doing so does not produce a sum that was already encountered
if(!sum[i]) {
for(sum[s = i] = 1, j = depth; j && !sum[s += arr[j - 1]]; j--) {
sum[s] = 1;
}
if(!j) {
// this is valid: set the value in arr[] and do a recursive call
arr[depth] = i;
search(arr, n, sum, max, str, depth + 1);
}
// whether the recursive call was processed or not, we have to clear the flags
// that have been set above
for(sum[s = i] = 0, k = depth - 1; k >= j; k--) {
sum[s += arr[k]] = 0;
}
}
}
}

int solve(int n, char * str) {
int     max = 0;              // best length so far
int     hi = n * (n + 1) / 2; // highest possible sum for n
uint8_t sum[hi + 1];          // encountered sums
uint8_t arr[n];               // array

memset(sum, 0, (hi + 1) * sizeof(uint8_t));
search(arr, n, sum, &max, str, 0);

return max;
}

/////////////////////////////////////////////////////////////////////////////////////

void main() {
char str[128];
int  n, res;

for(n = 1; n <= 19; n++) {
res = solve(n, str);
printf("N = %d --> %d with [ %s]\n", n, res, str);
}
}


Try it online!

• Thanks again! I wonder what speedups will be possible. – Anush Nov 9 '18 at 19:40
• @Anush Just compiling with -O3 allows to reach $N=19$ on TIO. – Arnauld Nov 9 '18 at 22:10
• Could you add the main function to your answer so people can just copy and paste? – Anush Nov 10 '18 at 19:13
• @Anush Sure. Done. – Arnauld Nov 10 '18 at 20:56

# Node.js, s = 17

Just a simple recursive search to get the ball rolling. Returns both the length and a valid array.

solve = n => {
var max = 0,  // best length so far
best,     // best array so far
sum = {}; // encountered sums

(search = a => {
var i, j, k, s;

// do we have a better array?
if(a.length > max) {
max = a.length;
best = [...a];
}

// try to prepend i = 1 to n to the current array
for(i = 1; i <= n; i++) {
// provided that doing so does not produce a sum that was already encountered
if((sum[j = 0, s = i] ^= 1) && a.every(n => sum[j++, s += n] ^= 1)) {
search([i, ...a]);
}
// reset the flags that have been toggled above
for(sum[s = i] ^= 1, k = 0; k < j; k++) {
sum[s += a[k]] ^= 1;
}
}
})([]);

return [ max, best ];
}


Try it online!

• Thank you for the first answer! – Anush Nov 9 '18 at 16:55