sandipdeveloper
BAN USERimport java.util.*;
/*
1. Recurse through array A, until you reach the last element (let's say ith)
2. Find all element on the array B which are greater than ith element in A
3. Add those elements in a set, put that set (let's call it result set) in a Map (let's call it dictionary) where key is the ith element in A
4. Now, recusrion call goes back to the previous (i-1) th element in array A
5. Find an element in the array B which is greater than (i - 1)th elemnt in A
6. If found, check if there in any elemnt in array A, from location (i-1) to arrayA.length
7. If found, let's say A[smallerThanB] add combination of A[i-1],element in B and result set of A[smallerThanB] in A to the result set of A[i-1]
also add A[i-1],element in B and elemnt found in A to result set of A[i-1], put the whole thing in dictionary
8. Keep recursing
*/
class TestMatch {
public void findMatchedArray(int[] arrA, int[] arrB, int position, Map<Integer, Set<String>> dictionary) {
if(position == arrA.length ) {
return;
}
findMatchedArray(arrA, arrB, position + 1, dictionary);
Set<String> matches = new HashSet<String>();
for(int countB = 0; countB < arrB.length; countB++) {
if(arrA[position] < arrB[countB]) {
matches.add(String.valueOf(arrA[position])+"-"+String.valueOf(arrB[countB]));
for(int _count = position; _count<arrA.length; _count++) {
if(arrA[_count] > arrB [countB] ) {
matches.add(String.valueOf(arrA[position])+"-"+String.valueOf(arrB[countB])+"-"+String.valueOf(arrA[_count]));
addElementsFromB(dictionary, matches, arrA[_count], arrA[position], arrB[countB]);
}
}
}
}
dictionary.put(arrA[position], matches);
}
private void addElementsFromB(Map<Integer, Set<String>> dictionary, Set<String> matches, int element, int elementA, int elementB) {
if(dictionary.containsKey(element)) {
Set<String> belongsToElement = dictionary.get(element);
Iterator itr = belongsToElement.iterator();
while(itr.hasNext()) {
matches.add(String.valueOf(elementA) +"-"+ String.valueOf(elementB) +"-"+ itr.next());
}
}
}
public static void main(String [] args) {
Map<Integer, Set<String>> dictionary = new HashMap<Integer, Set<String>>();
new TestMatch().findMatchedArray(new int[] {10, 15, 25, 40}, new int[] {1, 5, 20, 30, 50}, 0, dictionary);
Iterator mapItr = dictionary.keySet().iterator();
while(mapItr.hasNext()) {
Set<String> set = dictionary.get((Integer)mapItr.next());
Iterator setItr = set.iterator();
while(setItr.hasNext()) {
System.out.print(setItr.next()+",");
}
System.out.println();
}
}
}
looks like a series problem s = n(n+1)/2
- sandipdeveloper March 14, 2015public class FindMaxDays{
public int findDays(int candleNum, int maxDays, int level) {
if(maxDays*(1 + maxDays) >= 2*candleNum || level == 0) {
return maxDays;
}
else
return findDays(candleNum, maxDays + 1, level -1);
}
public int findMaxDays(int [] array) {
int sum = 0;
for(int count=0; count<array.length; count++) {
sum+=array[count];
}
return findDays(sum, 0, array.length);
}
public static void main(String [] args) {
System.out.println(new FindMaxDays().findMaxDays(new int[]{4,4,4}));
}
}
sorry for the duplicate post. Not able to delete this post.
- sandipdeveloper March 09, 2015
- sandipdeveloper September 07, 2015