CODEWITHSUNDEEP
javaalgorithmrecursiontime-complexity
javabeginner_0101
javabeginner_0101

Reputation: 31

Algorithm with O(n) to find min and max of triple product in subsets

The problem is to find the min and max triple product (product of 3 numbers) that can be formed, given an array of numbers. I managed to work out a code which works perfect, but it has got complexity (N^2). I need some help in reducing it to O(N) if possible.

Edit: Numbers can be both positive and negative.

Here's my code: 

import java.util.*;

class Result {

    public static int min =50000000;
    public static int max =-50000000;

    public static int solve(int pos, int currPro, int depth) {
            if (depth==3){
                check(currPro);
            }
            else {
                for (int i=1; i<=Triplet.data.length-pos; i++){
                if(pos+i < Triplet.data.length){
                    solve(pos+i,currPro*Triplet.data[pos+i],depth+1); 
                }
            }
        }
        return 0;
    }

    public static void check(int currPro) {
        if (currPro > max){
            max = currPro;
        }

        if (currPro < min){
            min = currPro;
        }
    }
}

class Triplet {

    static int[] data;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt(); //Number of int
        data = new int[num];
        for (int i=0;i<num;i++){
            data[i] = sc.nextInt();
        }
        if (num==3){
            int result= data[0]*data[1]*data[2];
            System.out.println(""+result+" "+result);
        }
        else{
            Result.solve(-1, 1, 0);
            System.out.println(""+Result.min+" "+Result.max);
        }
    }
}

Upvotes: 0

Views: 354

Answers (1)

Sergii Lagutin
Sergii Lagutin

Reputation: 10671

Try this

  1. Find three smallest and three largest numbers (regardless negative or positive ones) with quick sort partition in O(N) time.
  2. Apply your O(N^2) solution to array of 6 numbers.

Running time - O(N)

Upvotes: 4

Related Questions