Created
October 11, 2015 08:04
-
-
Save gansai/09f9a39f9a9a743df2ed to your computer and use it in GitHub Desktop.
Given an array, find a pair which sums up to a number (Sorted array solution)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
/** | |
* Created by gansai on 11/10/15. | |
*/ | |
public class FindPairSum_Sorted { | |
public static void main(String args[]) | |
{ | |
Integer array[] = new Integer[] { 1, 43, 2, 55, 21, 87, 9 }; | |
int sum = 76; | |
boolean foundPair = false; | |
List<Integer> list = new ArrayList<Integer>(Arrays.asList(array)); | |
/** | |
* Sorting in ascending order | |
*/ | |
// Collections.sort(list); // Way 1 - Sort it with natural ordering (increasing order) | |
/** | |
* Sorting in descending order | |
*/ | |
// Collections.sort(list); Collections.reverse(list);// Way 2 - Sort it, reverse it | |
//Collections.sort(list,Collections.reverseOrder()); // Way 3 - Sort the reversed collection. | |
/** | |
* Sorting in descending order - Way 4 - Writing a comparator. | |
*/ | |
Collections.sort(list, new Comparator<Integer>() { | |
@Override | |
public int compare(Integer o1, Integer o2) { | |
return o2.compareTo(o1); | |
} | |
}); | |
array = list.toArray(new Integer[list.size()]); | |
for(int i = 0; i< array.length; i++) { | |
System.out.print(array[i] + " "); | |
} | |
System.out.println(); | |
for(int i = 0, j= array.length-1; i< j;) | |
{ | |
if(array[i] + array[j] == sum) | |
{ | |
foundPair = true; | |
System.out.println("Found the pair which sums up to "+ sum); | |
System.out.println("They are "+ array[i] + " and " + array[j]); | |
break; | |
} | |
else if(array[i] + array[j] > sum) | |
{ | |
System.out.println("Moving left pointer to right"); | |
i++; continue; | |
} | |
else if(array[i] + array[j] < sum) | |
{ | |
System.out.println("Moving right pointer to left"); | |
j--; continue; | |
} | |
else { | |
break; | |
} | |
} | |
if(!foundPair) | |
{ | |
System.out.println("We could not find a pair which would sum up to "+ sum); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment