Optimizing the Partition of an Array

Question

I was solving a programming challenge question but my solution was giving timeout/error for large numbers. Can anyone help me to optimize my solution?

Question:

You are given an array A of N integers. Now you are required to fixed X such that the difference between the following two values is minimum:

 1. A[1] * A[2] * A[3] * ......... * A[X]
 2. A[X+1] * A[X+2] * ........... * A[N]

and if there is more value of X then print the smallest one.

Constraint:

• 1 <= 1 <= 10^5
• 1 <= A[i] <= 10^18

Input:

• The first line contains integer N (for size)
• The second line contains space separated numbers (for array)

import java.util.*;
public class Main
{
 public static void main(String[] args) {
 Scanner s=new Scanner(System.in)
 int size=Integer.parseInt(s.nextLine);
 long arr[]=new long[size];
 for(int i=0;i<=size;i++){
 arr[i]=s.nextLong();
 } 
 long part1=1,part2=1;
 long diff=1;long minIndex=0;long minNo=0;
 
 for(int k=0;k<size-1;k++){
 part1=1;part2=1;
 //minIndex=k;
 for (int i=0;i<=k ; i++){
 part1=part1*arr[i];
 } 
 for(int j=k+1;j<=size;j++){
 part2=part2*arr[j];
 }
 //System.out.println(part1+"---"+part2);
 diff=Math.abs(part1-part2);
 if(k==0){
 minNo=diff;
 minIndex=k;
 }
 //System.out.println(diff);
 if(minNo>diff){
 
 minNo=diff;
 minIndex=k;
 }
 
 
 }
 System.out.println("MinNo: "+minNo+" Index: "+minIndex);
 
 
 
 }
}

I was testing against this input

5
9090909090909009 780009090900909 898989898898898 98998 9999776765576765

The answer should be 2 (if counting from zero,then 1) but my code is giving 4.

• WJS: You are taking the product of very large numbers. These will exceed the max value of a long so you will need to use BigInteger.
• Andrew Scott: Wasn't this a part of a contest held recently in HackerEarth?
• Nandan Raj: Ya, it is. That contest is ended.

Answer 1

While the answer suggested by @Mukesh Prajapati works, there's still a much faster and better way to do this.

You can use log to shorten the values, so then you'd be just adding or subtracting the values from the log calculations because now addition means multiplication and subtracting means division. Now your problem is reduced to finding a point in the array where the sum of the left side elements is closest to the right side elements.

You store the cumulative sum for fast look ups. This enables you to quickly compute the left sum and the right sum of the array. The final minimum difference is in ans while the index is in index variable.

void partition(int n, vector<double> &a) {
 double total = 0; vector<double> sum_array_a;
 for(auto &x: a) {
 x = log10(x);
 total += x;
 sum_array_a.push_back(total);
 }
 double ans = INFINITY, index = -1;
 for(int i = 0; i < n; i++) { // Check for all points if you can split here
 double left = sum_array_a[i];
 double right = total - left; // Right side sum of elements
 double diff = abs(left - right);
 if(diff < ans) {
 ans = diff;
 index = i;
 }
 }
 printf("%f", index);
}

• Nandan Raj: Hi Andrew, I want know how to Implement this using log method.

Answer 2

It is unnecessary to calculate multiplication of subArray again and again. It is the reason why you are getting timeout error. You are using Long to store multiplication which will lead to wrong answer, you need to use BigInteger. Below approach will do multiplication only once. After that, you can simply iterate and find out differences between them.

import java.math.BigInteger;
import java.util.Scanner;
public class ParitionArray {
 public static void main(String[] args){
 Scanner s=new Scanner(System.in);
 int size=Integer.parseInt(s.nextLine());
 long arr[]=new long[size];
 for(int i=0;i<size;i++){
 arr[i]=s.nextLong();
 }
 long minIndex=0;
 BigInteger minNo=BigInteger.ZERO;
 BigInteger[] prefixedMult = new BigInteger[size];
 prefixedMult[0] = BigInteger.valueOf(arr[0]);
 for(int k =1; k< size; k++){
 prefixedMult[k] = prefixedMult[k-1].multiply(BigInteger.valueOf(arr[k]));
 }
 for(int k=0;k<size;k++){
 BigInteger part1 = prefixedMult[k]; //multiplication of A[1]*A[2]A[3].........*A[k]
 BigInteger part2 = prefixedMult[size-1].divide(part1); //multiplication of A[k+1]A[k+2]...........*A[size]
 BigInteger diff = part1.subtract(part2).abs();
 if(k==0){
 minNo=diff;
 minIndex=k;
 }
 //System.out.println(diff);
 if(minNo.compareTo(diff)==1){
 minNo=diff;
 minIndex=k;
 }
 }
 System.out.println("MinNo: "+minNo+" Index: "+minIndex);
 }
}

Input:

5
2
8
6
5
3

Output:

MinNo: 74 Index: 1

I found @AndrewScott answer to be helpful. Below is it's equivalent implementation in Java:

 public static void main(String[] args){
 Scanner s=new Scanner(System.in);
 int size=Integer.parseInt(s.nextLine());
 long arr[]=new long[size];
 for(int i=0;i<size;i++){
 arr[i]=s.nextLong();
 }
 long minIndex=0;
 Double minNo=Double.MAX_VALUE;
 Double[] prefixedMult = new Double[size];
 prefixedMult[0] = Math.log10((double)arr[0]);
 for(int k =1; k< size; k++){
 prefixedMult[k] = prefixedMult[k-1] + Math.log10((double)arr[k]);
 }
 for(int k=0;k<size;k++){
 Double part1 = prefixedMult[k]; //multiplication of A[1]*A[2]A[3].........*A[k]
 Double part2 = prefixedMult[size-1] - (part1); //multiplication of A[k+1]A[k+2]...........*A[size]
 Double diff = Math.abs(part1 - part2);
 if(minNo > diff){
 minNo=diff;
 minIndex=k;
 }
 }
 System.out.println("MinNo: "+minNo+" Index: "+minIndex);
 }

• Nandan Raj: HI,Thanks for suggesting bigInteger. With bigInteger I am getting correct answer. But, I can't quite understand your prefixedmult. A watch on "diff" variable returned 718 704 624 240 720, But It should be 718 74 81 477. So the final output should be MinNo: 74 Index: 1
• mukesh210: What is the input you are trying on?
• Nandan Raj: 5(size) 2 8 6 5 3
• Andrew Scott: For an input that small, it should work even on your code
• Andrew Scott: I doubt for the input constraints this code would work