A solution for nlogn can be -Take element one by one and subtract it with the sum u wanna achieve and then instead of searching the array linearly keep the sorted array with u and search in it using binary search only if the element is there do a linear search on the original array

@kb24 @vsaxena115 - Or you could achieve O(n) running time by storing the ice cream flavor prices in a hash table. So then you would just iterate through each of the prices, subtract the price from the money M that you have to spend, and then look up the difference in your hash table to see if there exists a flavor for that price. This would yield a runtime of O(n) + O(n) * O(1) = O(n).

I did it in O(n) by storing the index of the elements in an array.Initialize the index array with -1 and then store the index of each element.take the ith element and check whether the M-arr[i]'s index is>=0(means its present in the array) and the index!=i(to avoid repetation).It works for all test cases.

you can also solve it using two pointer algorithm..

Using array as index value , please give ur suggestion

public class Solution {

public static void main(String[] args) {

    Scanner sc=new Scanner(System.in);
    int t=sc.nextInt();
    for(int itr=0;itr<t;itr++)
        {

        int m=sc.nextInt();
        int n=sc.nextInt();
        int arr[]=new int[10000];
        int flag=0;

        for(int i=0; i<n ;i++)
            {
            int j=sc.nextInt();

            if(arr[j]==0)
            {
                arr[j]=i+1;
            }

            if(m>j && arr[m-j]!=(i+1) && arr[m-j]>0 && flag==0) //arr[m-j]!=(i+1) checks that it does not take the same index                                                                       both the time
                {
                flag=1;
                    System.out.println(arr[m-j]+" "+(i+1));
            }

        }

    }
}

}

This is what I came up with:

At most the dollar amount can be 10,000. And mathematically we know that it must be a sum of TWO integers. Lets say M is "6": 1+5 2+4 3+3 4+2 1+5

It repeats, so we only need to test M/2 cases. Great! Than, int index1 = Arrays.asList(array).indexOf(lo); int index2 = Arrays.asList(array).indexOf(hi);

if both != -1: success.

The stupid thing is though that you have to print the lowest index first... this should have been provided.

My algorithm at most took .16 seconds.

As a small perfomance tweak, you can exclude items >= (m) from calculating, because they will never have a pair.

code using maps i think its simple to understand

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while(t--){
        int n,m;
        cin>>m>>n;
        vector<int>v(n);
        map<int,int>maps;
        for(int i=0;i<n;i++){
            cin>>v[i];
            if(maps.find(v[i])!=maps.end()){
                cout<<maps[v[i]]+1<<" "<<i+1<<endl;
            }
            maps[m-v[i]]=i;            
        }
    }
    return 0;
}

order of n

#!/bin/python3

import sys

def icecreamParlor(n,m, a):
    # Complete this function
    d=dict()
    for i in range(n):
        if( a[i] in d and d[a[i]]!=0):
            print(d[a[i]],i+1)
            break
        if(a[i]<m):
            d[m-a[i]]=i+1
        
        

if __name__ == "__main__":
    t = int(input().strip())
    for a0 in range(t):
        m = int(input().strip())
        n = int(input().strip())
        arr = list(map(int, input().strip().split(' ')))
        icecreamParlor(n,m, arr)

void icecreamParlor(int m, int n, int* a, int *rs) { // Complete this function for(int i=0;i

I think my solution has O(n) time complexity and O(n) space complexity.

1. Loop through costs and build up hash table to map cost to ice cream type
2. Loop through costs again and see if money-cost is in hash table and the index is different than the current index

In Python 3 the code would look like this:

def icecreamParlor(money, costs):
    costs_map = {}
    for i, cost in enumerate(costs):
        costs_map[cost] = i
        
    for i, cost in enumerate(costs):
        remaining=money-cost
        if remaining in costs_map:
            if costs_map[remaining] != i:
                return sorted([i+1, costs_map[remaining]+1])

Java Solution in O(n)

static int[] icecreamParlor(int m, int[] arr) {
    int[] index = new int[2];
    Map<Integer,Integer> map = new HashMap<>();
    for(int i = 0; i < arr.length; i++) {
        if(map.containsKey(m - arr[i])) {
            index[0] = map.get(m - arr[i]);
            index[1] = i + 1;
            return index;
        }
        map.put(arr[i], i + 1);
    }
    return index;
}

i have a O(n) approach in java using maps. PS: this is my first discussion :)

import java.util.*; class Solution { public static void main(String args[]) { Scanner scan = new Scanner(System.in); int test =scan.nextInt(); for(int l=0;l

        HashMap<Integer,List<Integer>> hm=new HashMap<Integer,List<Integer>>();
        for(int i=1;i<=n;i++)
        {
            int b=scan.nextInt();
            hm.putIfAbsent(b,new ArrayList<>());
            hm.get(b).add(i);

        }

        for(Integer key:hm.keySet())
        {
            int search=money-key;
            if(search==key)
            {   
                int min=Math.min(hm.get(key).get(0),hm.get(key).get(1));
                int max=Math.max(hm.get(key).get(0),hm.get(key).get(1));
                System.out.println(min+" "+max);
                break;
            }
            else
            {   if(hm.containsKey(search))
                {
                int min=Math.min(hm.get(key).get(0),hm.get(search).get(0));
                int max=Math.max(hm.get(key).get(0),hm.get(search).get(0));

                System.out.println(min+" "+max);
                break;
                }
            }
        }


    }
}

}

If I declare freq[] first, all test cases passed, but if I declare arr[] first, two test cases failed. Can anyone explain why?

#include <bits/stdc++.h>
using namespace std;
int freq[10004]; //This passes
int arr[10004];  //for all test cases
//int arr[10004]; but this fails
//int freq[10004]; for two test cases

int main()
{
int t;

    cin >> t;
    for (int i = 0; i < t; i++)
    {
memset(freq, 0, sizeof(freq));
int m, n, ansi, val;
cin >> m >> n;
for (int j = 0; j < n; j++)
{
    cin >> arr[j];
    freq[arr[j]]++;
}
for (int j = 0; j < n; j++)
{
    freq[arr[j]]--;
    if (freq[m - arr[j]] > 0)
    {

        ansi = j;
        val = m - arr[j];
        cout << j + 1;
        break;
    }
    freq[arr[j]]++;
}
for (int j = ansi + 1; j < n; j++)
{
    if (val == arr[j])
    {
        cout << " " << j + 1 << endl;
        break;
    }
}
    }
    return 0;
    }

Splitting the list was a nice and different approach that you made and i liked it.

You can speed this up, doing the contains on a list is O(n) and contains in a set is O(1). If you keep a hash set of things you have seen and what index they map to then you can turn this O(N^2) solution into O(n)

Nice solution

This is not O(n) solution. It is O(n^2)

I was using a dictionary but was running into duplicate keys problem. Your solution helped me understand how to use dictinary in a more effiecent way.

Why is the correct answer for the last case 3 5 (4 + 2) and not 1 4 (3 + 3)?

I also wrote a C# solution but didn't get any error while reading the input in any of three test cases in this particular problem. Can you share the error text that you were getting?

Not sure if it's a better solution. This is the logic I used.

def icecreamParlor(m, arr):
    combos=list(combinations(arr,2))
    indexes=[]
    for i in range(len(combos)):
        if combos[i][0]+combos[i][1]==m:
            if arr.index(combos[i][0])!=arr.index(combos[i][1]):
                indexes.append([arr.index(combos[i][0])+1,arr.index(combos[i][1])+1])
            else:
                indexes.append([arr.index(combos[i][0])+1,arr.index(combos[i][1],arr.index(combos[i][0])+1)+1])
    indexes.sort()
    for i in range(len(indexes)):
        return indexes[i]

If you sort the flavours, a binary search could be used to check if the array contains a given value. The problem can also be solved without using a binary search though using alternative techniques, such as with using a hash map.

Need help with this problem