CareerCup

public class FindEqualSumSubset {

	public static void main(String[] args) {
		ArrayList<Integer> input = new ArrayList<Integer>();
		input.add(5);
		input.add(5);
		input.add(8);
		input.add(2);
		input.add(1);
		//input.add(6);
		//input.add(7);
		
		System.out.println(doLogic(input)? "Yes":"No");
	}
	
	public static int getSum(ArrayList<Integer> inputList){
		int sum = 0;
		for(Integer temp: inputList)
			sum += temp;
		return sum;
	}
	
	public static boolean checkForEqualSumSubsets(ArrayList<Integer> superSet){
		System.out.println("SuperSet : " + superSet);
		if(superSet.size() %2 == 1)
			return false; // superset contains odd number of elements
		int sum = getSum(superSet);
		if(sum %2 == 1)
			return false; // sum is not even - so subsets cant have equal sum of integers
		int subsetSize = superSet.size()/2;
		int fixedStart = 0, fixedEnd = 0, varStart = 1;
		sum = sum/2;
		while( fixedStart < superSet.size()-subsetSize){
			ArrayList<Integer> subset = createSubList(fixedStart, fixedEnd, varStart, subsetSize, superSet);
			if(subset.size() == subsetSize && (sum == getSum(subset))){
				return true;
			}
			
			varStart++;
			if(varStart >= superSet.size()){
				if(fixedEnd >= superSet.size()){
					fixedStart++;
					fixedEnd = fixedStart;
				} else {
					fixedEnd++;
					varStart = fixedEnd+1;
				}
			}
		}
		
		return false;
	}
	
	public static ArrayList<Integer> createSubList(int fixedStart, int fixedEnd, 
			int varStart, int subListSize, ArrayList<Integer> origList){
		
		System.out.println("FixedStart : " + fixedStart + ", FixedEnd : " + fixedEnd + 
				", VarStart : " + varStart);
		
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		if (origList != null){
			for(int i = fixedStart; i <= fixedEnd && i < origList.size(); i++){
				result.add(origList.get(i));
			}
			for(int i = varStart; result.size() < subListSize && i < origList.size(); i++){
				result.add(origList.get(i));
			}
		}
		
		return result;
	}
	
	public static boolean doLogic(ArrayList<Integer> input){
		if(input.size() %2 == 0)
			return false; // got an even length array
		
		for(int i = 0; i < input.size(); i++){
			ArrayList<Integer> temp = new ArrayList<Integer>(input);
			temp.remove(i);
			if(checkForEqualSumSubsets(temp))
				return true;
		}
		
		return false;
	}

}

#include <iostream>

using namespace std;

// function to increment the counters
int inc(int i, int a[], int n,int k)
{
	if (i<=0)
	{
		return (++a[0]);
	}
	a[i]++;
	if(a[i] >= (n - (k-i)))
	{
		a[i] = inc(i-1, a, n, k) + 1;
	}
	return a[i];
}

// function to check the end of loop
bool end_of_loop(int a[], int k, int n)
{
	bool res = true;
	for(int i = 0; i < k; i++)
	{
		res = res && (a[i] >= (n -(k+i-1)));
	}
	return res;
}


int main()
{
	// input array
	int arr[] = {1,2,3,4,5,6,7,8};
	// total number of elements in array
	int N = 8;
	// combination size 
	int K = 4;

	// indexes of size K
	int a[K];

	for(int i = 0; i<K;i++)
	{
		a[i] = i;
	}

	bool loop = end_of_loop(arr,K,N-1);
	int count = 0;
	//loop till all combinations are printed
	while(!loop)
	{
		for(int i = 0; i < K; i++)
		{
			cout << arr[a[i]] <<" - ";
		}
		cout <<endl;
		count++;
		// increment the counters
		inc(K-1, a, N,K-1);

		// check for end of loop
		loop = end_of_loop(a,K,N-1);
	}

	// total no of combinations
	cout << "Count -- "<<count<<endl;
	return 0;

}

Whoa! I completely overlooked that scenario. I guess your answer is the correct one.

yup.. didn't test it before posting it. Thanks for pointing out. Corrected now.

void maxproduct( int num[], int length)
{
	if(length >= 1)
	{
		int currStart, currEnd, maxStart, maxEnd;
		double currProd, prevProd, maxProd;

		prevProd = currProd = maxProd = num[0];
		currStart = 0;
		currEnd = -1;

		int i = 1;
		for( ; i < length; i++)
		{
			currProd = currProd * num[i];
			if(currProd < prevProd)
			{
				currEnd = i;
				if( prevProd > maxProd)
				{
					maxStart = currStart;
					maxEnd = currEnd-1;
					maxProd = prevProd;
				}
				currStart = i;
				currProd = num[i];
			}
			prevProd = currProd;
		}
	
		if (currProd > maxProd) // if the value at the end is greater...
		{
			maxStart = currStart;
			maxEnd = i-1;
			maxProd = currProd;
		}

		cout << "Range is : "<<maxStart<<" - "<<maxEnd<<" = "<<maxProd<<endl;
	}
	else
	{
		cout << "Empty Array"<<endl;
	}
}

There should not be a new string and allocating new memory for the extra characters alone will break the indexing of the string.

This logic has the possibility of returning the smallest element in the tree right? I guess there should be an extra check for non leaf node

void maxproduct( int num[], int length)
{
	int currStart, currEnd, maxStart, maxEnd;
	double currProd, prevProd, maxProd;

	prevProd = currProd = maxProd = num[0] // assuming non empty array, add checks
	currStart = 0;
	currEnd = -1;

	int i = 1;
	for( ; i < length; i++)
	{
		currProd = currProd * num[i];
		if(currProd < prevProd)
		{
			currEnd = i;
			if( prevProd > maxProd)
			{
				maxStart = currStart;
				maxEnd = currEnd;
				maxProd = prevProd;
			}
			currStart = i;
			currProd = num[i];
		}
		prevProd = currProd;
	}
	if(currEnd == -1 || currEnd < currStart)
	{
		currEnd = i;
		if (currProd > maxProd)
		{
			maxStart = currStart;
			maxEnd = currEnd;
			maxProd = currProd;
		}
	}

	cout << "Range is : "<<maxStart<<" - "<<maxEnd<<" = "<<maxProd<<endl;
}

The minimum no of moves will be 2*pow(n,2) + 3*n. Where n is the no of monsters.

The sequence for AAAA_BBBB is: (_ is the empty space)
AAA_ABBBB
AAABA_BBB
AAABAB_BB
AAAB_BABB
AA_BABABB
A_ABABABB
ABA_ABABB
ABABA_ABB
ABABABA_B
ABABABAB_
A_ABABAB_
ABA_ABAB_
A_A_ABAB_
A_ABA_AB_
ABA_A_AB_
A_A_A_AB_
A_A_ABA__
A_ABA_A__
ABA_A_A__
A_A_A_A__
A_A_A__A_
A_A_A___A
A_A_A____
A_A__A___
A_A___A__
A_A____A_
A_A_____A
A_A______
A__A_____
A___A____
A____A___
A_____A__
A______A_
A_______A
A________
_A_______
__A______
___A_____
____A____
_____A___
______A__
_______A_
________A

A classic kd tree problem in finding 'n' nearest neighbours for a given 2D point. Check this link : en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search