0

You are given two arrays A and B each containing n, integers. You need to choose exactly one number from A and exactly one number from B such that the index of the two chosen numbers is not same and the sum of the 2 chosen values is minimum.

Your objective is to find and print this minimum value.

For example in the image shown below is the minimum sum. enter image description here

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    static int twinArrays(int[] ar1, int[] ar2){
        // Complete this function
        int minAr1 = ar1[0];
        int minAr2;
        int index = 0;
        for(int i =0; i<ar1.length;i++) {
            if(ar1[i]<minAr1) {
                minAr1 = ar1[i];
                index = i;
            }
        }
        if(index == 0) {
            minAr2 = ar2[1];
        }else {
            minAr2 =ar2[0];
        }

        for(int j=0;j<ar2.length;j++) {
            if(j!=index && minAr2>ar2[j]) {
                minAr2 =ar2[j];
            }
        }
        return minAr1+minAr2;
     }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if(n>=2 && n<=1000000) {
        int[] ar1 = new int[n];
        for(int ar1_i = 0; ar1_i < n; ar1_i++){
            int temp1 = in.nextInt();
            if(temp1>=1&&temp1<=1000000) {
                ar1[ar1_i] = temp1;
            }
        }
        int[] ar2 = new int[n];
        for(int ar2_i = 0; ar2_i < n; ar2_i++){
            int temp2 = in.nextInt();
            if(temp2>=1&&temp2<=1000000) {
                ar2[ar2_i] = temp2;
            }
        }
        int result = twinArrays(ar1, ar2);
        System.out.println(result);
        }

    }
}

i have Implemented that is working fine but still something is missing so some test case failing could anyone give me some clue and hint to optimize my code if you find any defect in this code

Improve this question
3
  • what should happen if the array is holding repeated values? Commented Jun 12, 2017 at 16:08
  • @ΦXocę 웃 Пepeúpa ツ if repeated value it will work fine also Test public void test2() { int[] ar1 = {1,1,4,1,7}; int[] ar2 = {1,1,4,1,7}; System.out.println(solution.twinArrays(ar1, ar2)); assertEquals(2, solution.twinArrays(ar1, ar2)); } Commented Jun 12, 2017 at 16:14
  • Can you tell us what test cases are failing? I can't help if I don't know where it is failing. Because I don't see any defects and the optimization isn't terrible, but the test cases you are failing are likely specific checks you aren't doing that I would need to see. Commented Jun 12, 2017 at 16:15

4 Answers 4

Reset to default
2

Your code works by finding the minimum value from the first array, then finding the minimum value from the second array that isn't at the same position of the minimum in the first array. The problem with this approach is that it isn't guaranteed to find the overall minimum sum. For example, consider these small arrays:

 [0, 1], [0, 100]

Here, if you take the minimum value of the first array (0) and the minimum value of the second array that isn't at the same position (100), you get the sum 100. However, the correct sum to pick is the smallest value from the second array (0) and the second-smallest value from the first array (1) for a total of 1.

One observation that's useful here is that the minimum-sum pair must be one of the following:

  • The sum of the smallest values from each array.
  • The sum of the smallest value from one array and the second-smallest value from the other.

Your solution is on the right track here, except you don't consider taking the smallest from the second array and the second smallest from the first. Try editing your code to account for that case.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

One simple observation is that if minimum elements from both arrays are at different position, Sum of both elements would be an answer so after sorting answer in this case would be A[0]+B[0], but if both are at the same position, there are two possibilities for answer after sorting both the arrays.

Suppose we have two arrays A and B which are sorted in increasing order. Then there are two possible answers and the actual answer would be minimum of them.

  1. Take minimum possible number from array A so that number would be A[0] and now find the minimum possible number from array B such that index of that element is not equal to 0 so best possible choice would be B[1]. Therefore answer in this case is A[0]+B[1].
  2. Another possibility is that we consider minimum possible number from array B first and then go to choose a number from array A so here those numbers would be A[1] and B[0] respectively and thus answer in this case is A[1]+B[0].

Now for the final answer, we can take minimum of both these possible answers.

Final_Answer = min(A[0]+B[1],A[1]+B[0]);

If you don't want to sort the Arrays due to tight time constraint. You can just keep track of First and Second minimum element of both arrays and use it in place of A[0],A[1] in above equation respectively.

A sample code using first and second minimum, 

static int twinArrays(int[] ar1, int[] ar2){

    int first_minimum_ar1 = Integer.MAX_VALUE;
    int second_minimum_ar1 = Integer.MAX_VALUE;
    int index_ar1=-1;

    int first_minimum_ar2 = Integer.MAX_VALUE;
    int second_minimum_ar2 = Integer.MAX_VALUE;
    int index_ar2=-1;


    for(int i=0;i<ar1.length;i++)
    {
        int element = ar1[i];
        if(first_minimum_ar1>=element)
        {
            second_minimum_ar1=first_minimum_ar1;
            first_minimum_ar1=element;
            index_ar1=i;
        }
        else if(second_minimum_ar1>element)
        {
             second_minimum_ar1=element;
        }
    }

    for(int i=0;i<ar2.length;i++)
    {
        int element = ar2[i];
        if(first_minimum_ar2>=element)
        {
            second_minimum_ar2=first_minimum_ar2;
            first_minimum_ar2=element;
            index_ar2=i;
        }
        else if(second_minimum_ar2>element)
        {
             second_minimum_ar2=element;
        }
    }

    if(index_ar2!=index_ar1)
        return first_minimum_ar1+first_minimum_ar2;


    return Math.min(first_minimum_ar1+second_minimum_ar2,first_minimum_ar2+second_minimum_ar1);

}
Improve this answer

5 Comments

Why isn't A[0] + B[0] an option, provided that they're at different indices?
@templatetypedef Yup I forgot that case, If they are at different indices that would be an answer. I will edit the answer.
Hm, I wrote exactly the same code and it seems doesn't work when input arrays already sorted (1, 2, 3, 4, 5..) due to max integer overflow.
@artem_p, That is because we have initialized Minimum variables with Integer.MAX_VALUE. While returning the result we do summation of them so by chance if any of the variable is still Integer.MAX_VALUE then increment of 1 in it causes Integer.MIN_VALUE which will be negative so that wuold be wrong answer but still we will get that as a result of min(int a,int b) function. So here if given input is <10^9 we can use 10^9+1 as a maximum value to initialize minimum and if we have tight constraint with limit <= 2^31-1 you need to use there Long variable to store minimum value.
@SanketMakani .. It fails the following test case {1,2,3,4} {1,2,4,5}
0

What I did was, sort one array(ar1) in ascending order(take ar[0]) and the other in descending order(ar2) and then take (ar2[ar2.length-1]).

 class TwinArray{
    static int twinArrays(int[] ar1, int[] ar2){
       Arrays.sort(ar1);
       Integer[] Ar2 = new Integer[ar2.length];
        for (int i=0;i<ar2.length;i++)
            Ar2[i]=ar2[i];
         Arrays.sort(Ar2,Collections.reverseOrder());
    System.out.println(Ar2[Ar2.length-1]);
     return (ar1[0]+Ar2[Ar2.length-1]);
    }
public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] ar1 = new int[n];
        for(int ar1_i = 0; ar1_i < n; ar1_i++){
            ar1[ar1_i] = in.nextInt();
        }
        int[] ar2 = new int[n];
        for(int ar2_i = 0; ar2_i < n; ar2_i++){
            ar2[ar2_i] = in.nextInt();
        }
        int result = twinArrays(ar1, ar2);
        System.out.println(result);
    }
}
Improve this answer

Comments

0

This one will probably pass all of your test cases.

Runtime Complexity ~ o(n)

static int twinArrays(int[] ar1, int[] ar2){
        int ar1Minimum = Integer.MAX_VALUE , ar1MinIndex = -1;
        int ar1SecondMin = Integer.MAX_VALUE ;

        //Get the element with minimum value and index
        for(int i = 0 ; i < ar1.length ; ++i){
            if(ar1Minimum > ar1[i]){
                ar1Minimum = ar1[i]; ar1MinIndex = i;
            }       
        }


        //Get the second minimum 
        for(int i = 0 ; i < ar1.length ; ++i){
            if(ar1SecondMin > ar1[i] && i!=ar1MinIndex){ // i != ar1MinIndex = Important to avoid duplicate minimum values [1,1,2,4] min = 1 , secondMin = 2 and not 1
                ar1SecondMin = ar1[i]; 
            }       
        }

        int ar2Minimum = Integer.MAX_VALUE , ar2MinIndex = -1;
        int ar2SecondMin = Integer.MAX_VALUE ;

        for(int i = 0 ; i < ar2.length ; ++i){
            if(ar2Minimum > ar2[i]){
                ar2Minimum = ar2[i]; ar2MinIndex = i;
            }       
        }

        for(int i = 0 ; i < ar2.length ; ++i){
            if(ar2SecondMin > ar2[i] && i != ar2MinIndex){
                ar2SecondMin = ar2[i];
            }       
        }

        if(ar1MinIndex != ar2MinIndex){
            return ar1Minimum + ar2Minimum;
        }

        return Math.max((ar1Minimum + ar2SecondMin), (ar1SecondMin + ar2Minimum));


 }
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.