Wednesday, March 16, 2011

LCM of Array of Numbers

Finding LCM of all the elements of an array.
public static long calcLCM(int[] numArray) {
  if (null == numArray) {
   return -1;
  }
  int len = numArray.length;

  if (len < 2) {
   return -1;
  }
  int maxInArray = findMaxInArray(numArray);

  int countOnes = 0;
  boolean iFactor = true;
  long lcmOfNumbers = 1;

  for (int i = 2; i <= maxInArray; i++) {
   countOnes = 0;
   iFactor = true;
   while (iFactor) {
    iFactor = false;
    for (int j = 0; j < len; j++) {
     if ((numArray[j] > 1) && (numArray[j] % i == 0)) {
      numArray[j] = numArray[j] / i;
      iFactor = true;
     }
     if (numArray[j] == 1) {
      countOnes += 1;
     }
    }
    if (iFactor) {
     lcmOfNumbers *= i;
    }
   }
   if (countOnes == len) {
    break;
   }
  }

  return lcmOfNumbers;
 }


Approach:

A method using a table
This method works for any number of factors. One begins by listing all of the numbers vertically in a table (in this example 4, 7, 12, 21, and 42):
4
7
12
21
42
The process begins by dividing all of the factors by 2. If any of them divides evenly, write 2 at the top of the table and the result of division by 2 of each factor in the space to the right of each factor and below the 2. If they do not divide evenly, just rewrite the number again. If 2 does not divide evenly into any of the numbers, try 3.
x 2
4 2
7 7
12 6
21 21
42 21
Now, check if 2 divides again
x 2 2
4 2 1
7 7 7
12 6 3
21 21 21
42 21 21
Once 2 no longer divides, divide by 3. If 3 no longer divides, try 5 and 7. keep going until all of the numbers have been reduced to 1.
x 2 2 3 7
4 2 1 1 1
7 7 7 7 1
12 6 3 1 1
21 21 21 7 1
42 21 21 7 1
Now, multiply the numbers on the top and you have the LCM. In this case, it is 2 × 2 × 3 × 7 = 84. This is a variation on Euclid's algorithm, as common factors are essentially divided out along the way of dividing all of the numbers at once by each successive factor. You will get to the LCM the quickest if you use prime numbers and start from the lowest prime, 2.

No comments:

Post a Comment