# Ice Cream Parlor – Part II

I decided to try a different approach for a solution to the Binary Search: Ice Cream Parlor HackerRank challenge. On this pass I am using the HashMultimap class from Guava by Google.

Following is a screen capture of the Eclipse IDE console using the third test case:

```2 3
1 4
4 5
29 46
11 56
84 240
413 584
28 80
380 633
190 242
450 667
7 126
208 636
301 831
243 649
258 429
18 49
7 32
0 468
196 718
292 1236
539 935
20 263
30 107
3 94
425 484
0 550
219 656
133 242
0 244
317 338
207 485
63 64
13 206
0 388
654 972
205 275
0 195
471 633
371 393
25 170
64 521
28 78
949 1590
1 1043
636 773
0 136
6 47
81 288
274 983
```

My entire Java code which includes the methods and classes for the binary search and the hash map approaches follows:

```import java.util.Arrays;
import java.util.Collection;
import java.util.Map.Entry;
import java.util.Scanner;

/**
*
*/
class IceCream implements Comparable<IceCream> {

// **** members ****

int price;
int index;

/**
* Constructor
*/
public IceCream(int price, int index) {
this.price = price;
this.index = index;
}

/**
* Comparator.
*/
public int compareTo(final IceCream ic) {
return  Integer.compare(this.price, ic.price);
}
}

public class Solution {

/**
* Binary search.
*/
static int binSearch(int price, IceCream[] iceCreams) {
int lo = 0;
int hi = iceCreams.length - 1;

// **** ****

while (lo <= hi) {

// **** compute mid point ****

int mid = lo + (hi - lo) / 2;

// **** update hi limit ****

if (price < iceCreams[mid].price) { hi = mid - 1; } // **** update lo limit **** else if (price > iceCreams[mid].price) {
lo = mid + 1;
}

// **** found price ****

else {
return mid;
}
}

return -1;
}

/**
* Select and print the two flavors using binary search.
*/
static void selectFlavors(int money, IceCream[] iceCreams) {
int firstPrice 	= 0;
int secondPrice	= 0;

// **** sort array of ice cream ****

Arrays.sort(iceCreams);

// **** traverse the price array looking for two entries that add to money ****

for (int i = 0; i < iceCreams.length; i++) { // **** first price (from prices array) **** firstPrice = iceCreams[i].price; // **** check if price is too high for the money we have **** if (firstPrice >= money) {
continue;
}

// **** compute the second price ****

secondPrice = money - firstPrice;

// **** look up second ice cream ****

int mid = binSearch(secondPrice, iceCreams);

// **** look for the second price index and print solution (if needed) ****

if (mid != -1) {

// **** adjust mid (if needed) ****

if (i == mid) {
mid++;
}

// **** print result in order ****

if (iceCreams[i].index < iceCreams[mid].index) {
System.out.println((iceCreams[i].index + 1) + " " + (iceCreams[mid].index + 1));
} else {
System.out.println((iceCreams[mid].index + 1) + " " + (iceCreams[i].index + 1));
}

// **** all done ****

break;
}
}
}

/**
* Select and print two flavors using Guava's HashMultimap instead of binary search.
* !!! WORK IN PROGRESS !!!
*/
static void getFlavors(int money, LinkedHashMap<Integer, Integer> iceCreams) {
int firstPrice 	= 0;
int secondPrice = 0;

// **** could have load multimap in main :o( ****

Multimap<Integer, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, Integer> entry : iceCreams.entrySet()) {
multiMap.put(entry.getValue(), entry.getKey());
}

// **** traverse list of ice creams ****

for (int firstFlavor = 0; firstFlavor < iceCreams.size(); firstFlavor++) {

// **** get price of current ice cream ****

firstPrice = iceCreams.get(firstFlavor);

// **** compute second price of ice cream ****

secondPrice = money - firstPrice;
if (secondPrice < 0) {
continue;
}

// **** look for the second price in the multiMap ****

if (multiMap.containsKey(secondPrice)) {

// **** get index of the second flavor ****

if (multiMap.containsKey(secondPrice)) {

// **** ****

Collection<Integer> flavors = multiMap.get(secondPrice);

// **** ****

int[] flavorArr = new int[flavors.size()];
int i = 0;
for (Integer p : flavors) {
flavorArr[i++] = p;
}

// **** sort the array of flavors ****

Arrays.sort(flavorArr);

// **** select the second flavor ****

int secondFlavor = -1;
for (int f : flavorArr) {
if (f != firstFlavor) {
secondFlavor = f;
break;
}
}

// **** display flavors in specified order (smaller & larger) ****

if (firstFlavor < secondFlavor) {
System.out.println((firstFlavor + 1) + " " + (secondFlavor + 1));
} else {
System.out.println((secondFlavor + 1) + " " + (firstFlavor + 1));
}

// **** we are done ****

return;
}
}
}
}

/**
* Solution approach selections.
*/
static enum Approach {
BinarySearch,
HashMapSearch
}

/**
* Test code.
*/
public static void main(String[] args) {

// **** select approach to use ****

Approach approach = Approach.HashMapSearch;

// **** open scanner ****

Scanner in = new Scanner(System.in);

// **** number of test cases ****

int t = in.nextInt();

// **** loop once per test ****

for(int a0 = 0; a0 < t; a0++) {

// **** money ****

int m = in.nextInt();

// **** number of flavors ****

int n = in.nextInt();

// **** select approach ****

switch (approach) {
case BinarySearch:
IceCream a[] = new IceCream[n];

for(int a_i=0; a_i < n; a_i++){
a[a_i] = new IceCream(in.nextInt(), a_i);
}

// **** select and print flavors ****

selectFlavors(m, a);
break;

case HashMapSearch:

for(int flavor = 0; flavor < n; flavor++){
iceCreams.put(flavor, in.nextInt());
}

// **** select and print flavor ****

getFlavors(m, iceCreams);
break;
}
}

// **** close scanner ****

in.close();
}

}
```

If you have comments or questions regarding this or any other post in this blog please do not hesitate and send me a message. I will replay as soon as possible and will not use your name unless you allow me to do so.

John

john.canessa@gmail.com