CODEWITHSUNDEEP
javaarraysalgorithmsortingdynamic-programming
iammurtaza
iammurtaza

Reputation: 1007

Sort an array which results in maximum product of elements

I am working on a problem which involves taking an integer array as an input from the user. The program calculates product of the elements of the array. The calculation goes as follows: for eg, let the input be 56, 61, 2. Then the program first performs 56 * 61 = 3416, then modulo 3416 with 199 = 33. Now take the next element in the array, i.e., 2 and multiply it with the 33 = 66. The result would be 3416 + 33 = 3482. This is the calculation of the isotopes atom. Now if we can rearrange the elements of the array, i.e., 61, 2, 56; we could achieve the maximum product as follows:

61 * 2 = 122
122 * 56 = 6832
6832 + 122 = 6954

I have written program which plainly calculate the product of the input array but now I want to sort array as mentioned above. My program is as follows:

import java.util.*;
public class codevita1 {
    public static void main (String []args) {
        int num = 0;
        try {
            num = Integer.parseInt (args[0]);
        } catch (Exception e) {
            System.err.println ("Arguments not enough");
        }
        int arr[] = new int[num];
        for (int i = 1; i <= num; i++) {
            arr[i-1] = Integer.parseInt(args[i]);
        }
        new codevita1().calcEnery (arr);
    }

    private int calcEnergy (int elements[]) {
    int energy = 0;
    int t = 1;
    for (int i = 0; i < elements.length; i++) {
        if (i == 0) {
            energy = (elements[i] * elements[++i]);
        } else {
            energy += (t * elements[i]);
        }
        t = energy % 199;
    }
    return energy;
}
}

I have searched for dynamic programming and divide and conquer algorithm but I could not understand which algorithm will help me achieve my task. Please help me out with respect to which algorithm should I use and how?

Upvotes: 1

Views: 377

Answers (1)

Lurr
Lurr

Reputation: 861

Naive approach is to check every permutation, and it take O(n!) time.

Also you may notice that (a%199 * b)%199 = (a * b) %199 It allows us to check every way to split set of numbers in two nearly equal subsets. When we check on of ways to split, we can calculate t which remains after calculation energy for first subset as just product of all numbers in first subset % 199 it will remain constant regardless of order of elements in the subset. Then we can recursively calculate optimal order for both subsets.

There are C(n,n/2) ways to split n numbers in two subset if order of subsets does matter. C(n,n/2) < 2^n so total number of operation is less than 2^n * 2 * 2^(n/2) * 4 * 2^(n/4) * 8 * 2^(n/8) *... * 2 ^ (log(n)/2) * 2^(2) * 2 ^ (log(n)) * 2 ^ 1 which is ~ 2^(2*n + 2*log(n)) which is O(2^n) so still very slow but better than n!

I suspect that it's may be much better to split in more subsets (more precisely sqrt(n) subsets sqrt(n) elements in each) but didn't yet calculate complexity for this case.

Upvotes: 1

Related Questions