CODEWITHSUNDEEP
arraysmathlcm
simplfuzz
simplfuzz

Reputation: 12905

Computing LCM of M consecutive numbers in an array of N integers

I came across this problem here. It was a programming contest held earlier this year.
Here is the summary :
Given an array of N integers, find LCM of all consecutive M integers.
For e.g. 

Array = [3,5,6,4,8] (hence N = 5)  
M = 3

Output : 

LCM(3,5,6) = 30  
LCM(5,6,4) = 60  
LCM(6,4,8) = 24

In fact there's a solution sketch here but I couldn't understand the Dynamic Programming Part.
So if someone could elaborate on the same solution with some examples it will be great.
A new, easy to understand solution will also be appreciated.

Upvotes: 1

Views: 1362

Answers (1)

Skrodde
Skrodde

Reputation: 41

I can not access the solution any more (maybe the link is broken?), but here is what I would do: I would have my program work like a pyramid. On the lowest row, I would have the array with the given numbers. On each row above, I would have an array with one field less than the array below. It would store the LCM of two values from the array below.

[   30    ]
[ 15,  30 ]
[3,  5,  6]

This way you can work with a recursive function and you have to build M-1 layers of the pyramid. Here's a Pseudo-Code implementation:

rekursivePyramid (Integer[] numbers, Integer height) {
    if (height == 0) return numbers;
    else {
        newNumbers = Integer[numbers.size() - 1];
        for (i=0; i<newNumbers.size(); i++) {
            newNumbers[i] = LCM ( numbers[i], numbers[i+1]);
        }
        return rekursivePyramid( newNumbers, height-1);
    }
}

This will give you an array, where you find the LCM of the first M numbers in first field, the LCM from the second to the M+1st number in the second field, etc.

Upvotes: 0

Related Questions