Arithmetic Progressions

October 24, 2017

I continue today working through my backlog of homework problems:

Given an array of at least three distinct positive integers sorted in ascending order, find all triples of array elements that form an arithmetic progression, so that the difference between the first and second elements is the same as the difference between the second and third elements. For instance, in the array (1 2 3 4 6 7 9) there are five triplets in arithmetic progressions: (1 2 3), (2 3 4), (2 4 6), (1 4 7), and 3 6 9).

Your task is to write a program that finds all the arithmetic progressions in an array; for extra credit, do the same thing for geometric progressions, where the ratios of the first to second element and the second to third elements are the same. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Posted by programmingpraxis

Filed in Exercises

11 Comments »

11 Responses to “Arithmetic Progressions”

The Visualizer said
October 24, 2017 at 4:50 PM
It’s an interesting problem indeed.
It makes me wonder – can one formulate a program to find harmonic progressions of a similarly created array?

Daniel said

October 25, 2017 at 4:28 AM

Here’s a solution in C++11.

/* arithmetic_progressions.cpp */

#include <array>
#include <stdio.h>
#include <vector>

using std::array;
using std::vector;

typedef unsigned int uint;

void arithmetic_progressions(
        const vector<uint>& v, vector<vector<uint>>* output) {
    for (size_t j = 1; j < v.size() - 1; ++j) {
        uint val_j = v[j];
        size_t i = j - 1;
        size_t k = j + 1;
        while (true) {
            if (i < 0 || k >= v.size()) break;
            uint val_i = v[i];
            uint val_k = v[k];
            uint i_diff = val_j - val_i;
            uint k_diff = val_k - val_j;
            if (i_diff == k_diff) {
                output->push_back({val_i, val_j, val_k});
            }
            if (k_diff > i_diff) {
                --i;
            } else {
                ++k;
            }
        }
    }
}

int main() {
    vector<uint> v = {1, 2, 3, 4, 6, 7, 9};
    vector<vector<uint>> output;
    arithmetic_progressions(v, &output);
    for (const auto& p : output) {
        printf("[%d,%d,%d]\n", p[0], p[1], p[2]);
    }
}

Build/Run:

$ g++ -std=c++11 -o arithmetic_progressions arithmetic_progressions.cpp
$ ./arithmetic_progressions

Output:

[1,2,3]
[0,2,4]
[2,3,4]
[0,3,6]
[2,4,6]
[1,4,7]
[3,6,9]

Daniel said

October 25, 2017 at 5:02 AM

Here’s my updated, code, fixing a bug in my last post. My bug arises from checking if unsigned int i is less than 0. I changed size_t to int for that variable.

I originally used ints and my program worked. I changed to size_t and didn’t check if the output was still correct, which led to the bug in my earlier post.

/* arithmetic_progressions.cpp */

#include <array>
#include <stdio.h>
#include <vector>

using std::array;
using std::vector;

typedef unsigned int uint;

void arithmetic_progressions(
        const vector<uint>& v, vector<vector<uint>>* output) {
    for (size_t j = 1; j < v.size() - 1; ++j) {
        uint val_j = v[j];
        int i = j - 1;
        size_t k = j + 1;
        while (true) {
            if (i < 0 || k >= v.size()) break;
            uint val_i = v[i];
            uint val_k = v[k];
            uint i_diff = val_j - val_i;
            uint k_diff = val_k - val_j;
            if (i_diff == k_diff) {
                output->push_back({val_i, val_j, val_k});
            }
            if (k_diff > i_diff) {
                --i;
            } else {
                ++k;
            }
        }
    }
}

int main() {
    vector<uint> v = {1, 2, 3, 4, 6, 7, 9};
    vector<vector<uint>> output;
    arithmetic_progressions(v, &output);
    for (const auto& p : output) {
        printf("[%d,%d,%d]\n", p[0], p[1], p[2]);
    }
}

Build/Run:

$ g++ -std=c++11 -o arithmetic_progressions arithmetic_progressions.cpp
$ ./arithmetic_progressions

Output:

[1,2,3]
[2,3,4]
[2,4,6]
[1,4,7]
[3,6,9]

David Liu said

October 25, 2017 at 2:41 PM

Great puzzle! My solution in Python:

def array_threes(arr1):
    # Takes a larger array and returns all the permutations smaller arrays of size 3.

    for i in arr1[:-2]:
        for j in arr1[i:-1]:
            for k in arr1[j:]:
                yield([i,j,k])

def array_diff(arr1):
    # Takes the difference between successive numbers in an array
    diff = []
    arr2 = arr1[1:]
    
    for a2, a1 in zip(arr2, arr1):
        diff.append(a2 - a1)

    return(diff)

      
def arith_prog(arr1):
    # Finds size-3 arithmetic progressions in an any sized array
    threes = []
    
    for threes in array_threes(arr1):
        diff = array_diff(threes)
        if diff[0]==diff[1]:
            yield(threes)

array_test = [1, 2, 3, 4, 6, 7 ,9]

for y in arith_prog(array_test):
    print(y)

programmingpraxis said
October 25, 2017 at 6:30 PM
@DavidLiu: Your solution takes cubic time to find the triples, the suggested solution takes linear time.
Daniel said
October 25, 2017 at 11:48 PM
“…the suggested solution takes linear time.”

@programmingpraxis, quadratic time, as you mention in the solution.
programmingpraxis said
October 26, 2017 at 12:44 AM
@Daniel. You are correct. I correctly stated the time complexity of the suggested solution as quadratic in the text of the exercise, but incorrectly stated that it is linear in my comment.

My comment about the time complexity of David Liu’s solution stands: the triply-nested loops
```
for i ... for j ... for k ...
```
in array_threes take cubic time.

Paul said

October 26, 2017 at 11:57 AM

In Python.

def prog(arr):
    n = len(arr)
    for j, aj in enumerate(arr):
        i, k, target = 0, n-1, 2*aj
        while i < j < k:
            test = arr[i] + arr[k]
            if test == target:
                yield arr[i], aj, arr[k]
                i, k = i+1, k-1
            elif test > target:
                k -= 1
            else:
                i += 1

Jan Van lent said

October 27, 2017 at 4:33 PM

Another Python solution. Using set is convenient. Bisection on x[j+1:] would also work.

def ap3(x):
    # x assumed sorted
    n = len(x)
    s = set(x[2:])
    for i in range(n-2):
        for j in range(i+1, n-1):
            xk = x[j] + (x[j] - x[i])
            if xk in s:
                yield (x[i], x[j], xk)

x = [1, 2, 3, 4, 6, 7, 9]
print(list(ap3(x)))

Paul said

October 28, 2017 at 6:39 AM

Another version. This is faster (in Python) than doing the scan.

def prog(arr):
    S = set(arr)
    for a, b in combinations(arr, 2):
        if 2*b - a in S:
            yield a, b, 2*b - a

Zack said

November 10, 2017 at 4:53 AM

That’s a nifty little problem. Here is my take on it, using Julia…

IsArithmetic{T <: Real}(x::Array{T, 1}) = (2x[2] == x[1] + x[3])
IsGeometric{T <: Real}(x::Array{T, 1}) = (x[2]^2 == x[1] * x[3])
IsHarmonic{T <: Real}(x::Array{T, 1}) = (x[2] == (2x[1]*x[3] / (x[1] + x[3])))

function main{T <: Real}(x::Array{T, 1}, pt::AbstractString = “a”)
pt = lowercase(pt)
n = length(x)

if pt == "a"
    println("Searching for Arithmetic progressions...\n")
    check = IsArithmetic
elseif pt == "g"
    println("Searching for Geometric progressions...\n")
    check = IsGeometric
elseif pt == "h"
    println("Searching for Harmonic progressions...\n")
    check = IsHarmonic
else
    println("Progression parameter should be one of the following: a, g, or h")
    return
end

for i = 1:(n-2)
    for j = (i+1):(n-1)
        for k = (j+1):n
            z = [x[i], x[j], x[k]]
            if check(z); println(z); end
        end     
    end
end

return

end

BTW, I figured it would be nice to include the Harmonic progression option, since that’s an interesting series to consider…

Programming Praxis