##### Ice Cream Parlor Hackerrank

Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool together m dollars for ice cream. On any given day, the parlor offers a line of n flavors. Each flavor, i, is numbered sequentially with a unique ID number from 1 to n and has a cost, c_{i}, associated with it.

Given the value of m and the cost of each flavor for t trips to the Ice Cream Parlor, help Sunny and Johnny choose two flavors such that they spend their entire pool of money (m) during each visit. For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second.

Note: Two ice creams having unique IDs i and j may have the same cost (i.e., c_{i} = c_{j}).

**Input Format**

The first line contains an integer, t, denoting the number of trips to the ice cream parlor. The 3t subsequent lines describe all of Sunny and Johnny’s trips to the parlor; each trip is described as follows:

The first line contains m.

The second line contains n.

The third line contains n space-separated integers denoting the cost of each respective flavor. The i^{th} integer corresponding to the cost, c_{i}, for the ice cream with ID number i (where 1<=i<=n).

**Constraints**

1<=t<=50
2<=m<=10^{4}

2<=n<=10^{4}

1<=c_{i}<=10^{4} , where i [1,n]

It is guaranteed that there will always be a unique solution.

**Output Format**

Print two space-separated integers denoting the respective ID numbers for the flavors they choose to purchase, where the smaller ID is printed first and the larger ID is printed second. Recall that each ice cream flavor has a unique ID number in the inclusive range from 1 to n.

**Sample Input**

```
2
4
5
1 4 5 3 2
4
4
2 2 4 3
```

**Sample Output**

```
1 4
1 2
```

**Explanation**

Sunny and Johnny make the following two trips to the parlor:

The first time, they pool together m=4 dollars. There are five flavors available that day and flavors 1 and 4 have a total cost of 1+3=4. Thus, we print 1 4 on a new line.

The second time, they pool together m=4 dollars. There are four flavors available that day and flavors 1 and 2 have a total cost of 2+2. Thus, we print 1 2 on a new line.

##### Solution

Naive Solution

Run a nested loop where the first (outer) loop corresponds to the first flavor and the second (inner) loop corresponds to the second flavor.

Once the first valid solution is found (i.e., c_{i}+c_{j}=m), break the loop and print your answer.

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int t;cin>>t; while(t--) { int m,n,j;cin>>m>>n; int a[n]; for(int i=0;i<n;i++) {j=0; cin>>a[i]; while(a[j]+a[i]!=m&&j<i) ++j;// searching of j where a[j]+a[i]=m if(a[i]+a[j]==m&&i>j){ cout<<j+1<<" "<<i+1<<endl;break;} } cin.ignore(numeric_limits<streamsize>::max(), '\n'); } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }

```
// Naive Java Solution
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t = scan.nextInt();
while(t-- > 0) {
int m = scan.nextInt();
int n = scan.nextInt();
int[] menu = new int[n];
for(int i = 0; i < n; i++) {
menu[i] = scan.nextInt();
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
if(menu[i] + menu[j] == m) {
System.out.println( (i + 1) + " " + (j + 1) );
break;
}
}
}
}
scan.close();
}
}
```

Complexity O(n^{2})

new solution for O(n)

#include <bits/stdc++.h> using namespace std; int frequency[10004]; int price[10004]; int main() { int test, n, m, c_i, c_j; cin >> test; for (int t = 1; t <= test; t++) { memset(frequency, 0, sizeof(frequency)); cin >> m >> n; for (int i = 1; i <= n; i++) { scanf("%d", &price[i]); frequency[price[i]]++; } int c_i_index; for (int i = 1; i <= n; i++) { c_i = price[i]; // Decrease the frequency to avoid counting value twice frequency[c_i]--; int tmp_c_j = m - price[i]; if (frequency[tmp_c_j] > 0) { c_j = tmp_c_j; c_i_index = i; printf("%d", i); break; } frequency[c_i]++; //Restore original frequency } // Search for c_j in the rest of the array for (int i = c_i_index + 1; i <= n; i++) { if (price[i] == c_j) { printf(" %d\n", i); break; } } } }

```
T = input()
for t in range(T):
C = input()
L = input()
costs = [int(c) for c in raw_input().split()]
done = False
for i in range(L):
for j in range(i+1,L):
if costs[i] + costs[j] == C:
print '%d %d'%(i+1,j+1)
done = True
break
if done:
break
```

```
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int k = 0; k < n; k++){
int C = sc.nextInt();
int P = sc.nextInt();
int [] p = new int[P+1];
for(int i = 1; i <= P;i++)p[i] = sc.nextInt();
for(int i = 1; i <= P; i++){
for(int j = i+1; j <= P; j++){
if(p[i]+p[j] == C){
System.out.println(i + " " + j);
break;
}
}
}
}
sc.close();
}
}
```

All rights reserved. No part of this Post may be copied, distributed, or transmitted in any form or by any means, without the prior written permission of the website admin, except in the case of brief quotations embodied in critical reviews and certain other noncommercial uses permitted by copyright law. For permission requests, write to the owner, addressed “Attention: Permissions Coordinator,” to the admin @coderinme