find complementary numbers

Find K Complementary numbers from array Java implementation

Find K complementary numbers from the given array

This is another approach to the problem that I have done it here. On that post, a good deal of visitors pointed out that it is actually o(n*n) not o(n) as I claimed.

Yes, the naive usage of Hashmap for holding the numbers has soared the performance and I have changed the approach as follows.

To remind the k complementary problem and its solution, you are given array of numbers and a number k of which you are going to find numbers that give k complementary. The following is an example of it.

The problem is, given numbers like 7, 1, 5, 6, 9, 3, 11, -1 and given number 10, write a script that would print numbers that would add to 10. In the example, it would be like
7 and 3, 1 and 9, -1 and 11.

Thanks Reda and mtrad for your correction.


package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * Algorithm to find the pairs making the K complementary in O(n) complexity
 * 
 * @author http://gullele.com
 */
public class KComplementary2 {
	
	public static void main(String[] args) {
		KComplementary2 kcomp = new KComplementary2();
		int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
		
		for (Integer number : kcomp.getKComplementaryPairs(10, numbers)) {
			System.out.println(" Pairs are "+ number + " and " + (10-number));
		}
	}
	
	public KComplementary2() {}
	
	/**
	 * An algorithm to find the pair from the given array that would sum up the given K
	 * 
	 * @note - the algorithm would be done in o(n)+o(nlogn). First it will run through the whole 
	 * numbers and creates a temporary list of pairs in HashMap with 
	 * (value, sum-value). 
	 * @param sum
	 * @param listOfIntegers
	 * @return
	 */
	public List getKComplementaryPairs(int sum, int[] listOfIntegers) {
		
		/*
		 * The algorithm works using front and last pointers on ascendingly sorted array. The front would be 
		 * instantiated with 0 and last with length-1; if the arr[front]+arr[last] == sum, then pick
		 * the numbers and add them to the pair array.
		 * if their sum is greater than sum, it means time to check the  second higher number that is lower
		 * than the current highest number. And the reverse would hold true if the sum is less than the sum
		 * time to move to the next higher number from the lower side.
		 */
		if (listOfIntegers == null || listOfIntegers.length == 0) {
			return null;
		}
		
		//quick sort the array 
		quickSort(0, listOfIntegers.length-1, listOfIntegers);
		
		int[] sortedArray = listOfIntegers;
		
		//holder for the complementary pairs
		List pairs = new ArrayList();
		int frontPointer = 0;
		int lastPointer = sortedArray.length-1;
		
		while (frontPointer < lastPointer) {
			int currentSum = sortedArray[frontPointer] + sortedArray[lastPointer];
			if (currentSum == sum) {
				/*
				 * Since sum is found, increment front and decrement last pointer
				 * Only one number is required to be hold, the other can be found 
				 * from sum-number since complementary 
				 */
				pairs.add(sortedArray[frontPointer]);//adding is o(1)
				frontPointer++;
				lastPointer--;
			} else if (currentSum > sum) {
				lastPointer--;
			} else {
				frontPointer++;
			}
		}
		
		return pairs;
	}
	
	/**
	 * sort the numbers. I have used quick sort here. QuickSort is nlogn in average case 
	 * well, in worst case it still would be n**2 though :(
	 * @param numbers
	 * @return sorted array numbers.
	 */
	public void quickSort(int lowerIndex, int higherIndex, int[] numbers) {
		/*
		 * Recursively inarray sort. Start from arbitrary value to compare from and recursively sort its 
		 * left and right.
		 */
		int pivot = lowerIndex+(higherIndex-lowerIndex)/2;
		int lower = lowerIndex;
		int higher = higherIndex;
		
		while (lower < higher) {
			while (numbers[lower] < numbers[pivot]) {
				lower++;
			}
			while (numbers[higher] > numbers[pivot]) {
				higher--;
			}
			
			//swap those needed to be on the left on those on the right.
			if (lower <= higher) {
				int temp = numbers[lower];
				numbers[lower] = numbers[higher];
				numbers[higher] = temp;
				lower++;
				higher--;
			}
		}
		if (lowerIndex < higher) {
			quickSort(lowerIndex, higher, numbers);
		}
		
		if (lower < higherIndex) {
			quickSort(lower, higherIndex, numbers);
		}
	}
}

Love algorithms? See how you would solve the following

Can you find the three numbers that would sum to T from given array?

From a file of billion numbers, find missing numbers with limited memory

Find longest palindrom from sequence of characters

Given the string, find the longest palindrom you can form from it


/**
 * @author gullele.com
 */
public class LongestPalindrom {
	public static void main(String[] args) {
		LongestPalindrom longest = new LongestPalindrom();
		System.out.println(longest.longest("zzbmbmbdmm"));
	}
	
	public String longest(String string) {
		if (string.length() == 0 || string == null) {
			return "";
		}
		

		StringBuffer palindrom = new StringBuffer();
		Map charBag = new HashMap();
		for (Character c : string.toCharArray()) {
			int totalChar = charBag.get(c) != null ? charBag.get(c) : 0;
			if ((totalChar + 1) % 2 == 0) {
				palindrom.append(c);
				palindrom = palindrom.insert(0, c);
				charBag.remove(c);
				continue;
			}
			charBag.put(c, ++totalChar);
		}
		
		if (charBag.size() > 0) {
			Iterator it = charBag.entrySet().iterator();
			Map.Entry pair = (Map.Entry)it.next();
			String c = pair.getKey().toString();
			palindrom.insert(palindrom.length()/2, c);
		}
		return palindrom.toString();
	}
}

Check if there are three numbers a, b, c giving a total T from array A

I got this question while helping a friend on the course work. It is relatively simple question. But the way how it is approached can make a difference on efficiency.

The question is, given an array of numbers, you are to find if there are three numbers that would total the given number T.

If done in a very naive way, it can soar to o(n^3) like having three loops and checking the sum inside the third loop.. well.. this is a no no..

I have approached it in a log n ( for sorting) and n for (searching) approach..


package algorithm;

import java.util.Arrays;

/**
 * Given an array of integers, find if there are three numbers that would sum up to the 
 * number T
 * 
 * @author http://gullele.com
 *
 */
public class ThreeNumbersSummingT {
	public static void main(String[] args) {
		int[] test = new int[]{1,3,4,5,10,12, 18};
		ThreeNumbersSummingT summt = new ThreeNumbersSummingT();
		
		int[] response = summt.findThreeNumbers(test, 29);
		
		if (response.length > 1) {
			for(int num : response) {
				System.out.println(num);
			}
		} else {
			System.out.println(":( Couldn't find those three gems");
		}
				
	}
	
	public int[] findThreeNumbers(int[] nums, int t) {
		
		int[] indexes = new int[1];
		if (nums.length == 0 || nums.length <= 2) {
			return indexes;
		}
		
		//for primitive this would be quick sort so we have nlogn
		Arrays.sort(nums);
		
		int minIndex =0;
		int maxIndex = nums.length-1;
		int current = 1;
		while (minIndex != maxIndex) {
			if (nums[minIndex] + nums[maxIndex] + nums[current] == t) {
				int[] summingNumbers = new int[3];
				summingNumbers[0] = nums[minIndex];
				summingNumbers[1] = nums[current];
				summingNumbers[2] = nums[maxIndex];
				return summingNumbers;
			}
			
			int lookingFor = t-(nums[minIndex] + nums[maxIndex]);
			//if the number being sought is beyond the max, then jack up the min index
			if (lookingFor >= nums[maxIndex]) {
				minIndex++;
				current = minIndex + 1;
			} else if (nums[minIndex] + nums[maxIndex] + nums[current] < t) {
				current++;
			} else {
				maxIndex--;
				current = minIndex + 1;
			}
			
		}
		
		return indexes;
	}
}