Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1352

Question Name: Two Numbers With Sum

Question Description: within a sorted integer array, find two integers, whose sum is the given target value. If there are multiply pairs, find the one with the smallest product.

Input: the input might contain multiple test cases. Inside each test case, the first line includes two integers N and N (1 <= N <= 10^6), saying the number of items in the array and the target number. The second line contains N integers as the content of the array.

Output: print the two numbers, with the smaller one firstly, if they exist. Otherwise, print “-1 -1”.

1 2 3 4 5 | Input: 6 15 1 2 4 7 11 15 Output: 4 11 |

This challenge is a variant of the 2-sum problem. And the outtest pair holds the smallest product.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/08/2014 * Last updated: 09/08/2014 * * Filename: TwoNumbersWithSum.java * Compilation: javac TwoNumbersWithSum.java * Execution: java TwoNumbersWithSum * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * An utility to find the two numbers in a array, whose sum is equal to * the given target. If there are multiply pairs, find the one with the * smallest product. * @author Sheng Yu codesays.com */ public class TwoNumbersWithSum { /** * Find the two numbers in a array, whose sum is equal to the given * target. If there are multiply pairs, find the one with the smallest * product. * @param input a sorted integer array to find two numbers. * @param target the required sum of the two numbers. */ public static void twoSum(int[] input, int target) { // A variant of N-Sum problem. // http://en.wikipedia.org/wiki/3SUM int begin = 0, end = input.length - 1, temp; while (begin < end) { temp = input[begin] + input[end]; if (temp == target) { System.out.print(input[begin]); System.out.print(" "); System.out.println(input[end]); return; } else if (temp > target) { --end; } else { ++begin; } } // Did not find the 2-sum System.out.println("-1 -1"); return; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int[] input = null; int target = 0; while (st.nextToken() != StreamTokenizer.TT_EOF) { input = new int[(int) st.nval]; st.nextToken(); target = (int) st.nval; for (int i = 0; i < input.length; ++i) { st.nextToken(); input[i] = (int) st.nval; } twoSum(input, target); } } } |