Given a sequence of length N, find the number of segments needed to divide the sequence in groups of K, where each group overlaps with the next.

segs.c

/* cc -lm segs.c -o segs */

/* Problem:
 *
 * Given a sequence of length N, find the number of
 * segments needed to divide the sequence in groups
 * of K, where each group overlaps with the next.
 *
 * e.g., Given the sequence 1,2,3,4,5,6,7,8,9 of length 9
 * when divided in groups of 3 will become:
 *   [1,2,3] [3,4,5] [5,6,7] [7,8,9]
 * which results in 4 segments.
 */

/* Solution:
 *
 * Overlapping neighbor segments increase the length of
 * the sequence that we must fit in the segments.
 * The following is trying to find the new length of
 * the sequence; the initial sequence length increased
 * by the number of duplicated overlapping elements.
 * The length is then divided to the group size, thus
 * returning the number of segments.
 * That number may not be an integer, which indicates
 * that the last segment is not filled completely.
 * To include that last segment, the result is always
 * rounded up.
 *
 * initial algorithm:
 *   a. (N + (N-K) / (N-1)) / K
 * alternative forms:
 *   b. (N-1) / (K-1)
 *   c. N/(K-1) - 1/(K-1)
 */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

int
main(void) {
	size_t N = 9;
	size_t K = 2;

	if (1 == K) printf("N=%zd K=%zd #segments=%zd\n", N, K, N);

	for (K=2; K<=N; K++) {
		// double s = (N + (double)(N-K)/(K-1)) / K;
		double s = (double)(N-1)/(K-1);
		printf("N=%zd K=%zd #segments=%f\n", N, K, ceil(s));
	}

	return EXIT_SUCCESS;
}