kb24 I can think of using nested for loops.Can someone please share the approach to a solution better than o(n^2) ?
vsaxena115 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
akrox58 Wont this be n2logn? Binary search itself is nlogn and we are running a loop for o(n). so it will be n*nlogn right? Or am I misunderstanding something?
akrox58 Also, sorted array means you will have to take extra memory. It's better to do linear search itself! Plus managing duplicates is also difficult!
lizzael_v_c Managing duplicates is not so hard.
private static object Sol(int[] data, int n, int m) { var dict = GetDict(data, n); for (var p = 0; p < n; p++) { var dif = m - data[p]; if (dict.ContainsKey(dif)) { var list = dict[dif]; if (list[0] != p) return FormatResult(p, list[0]); if (list.Count > 1) return FormatResult(p, list[1]); } } return ""; // Should never happen. } private static Dictionary<int, List<int>> GetDict(int[] data, int n) { var dict = new Dictionary<int, List<int>>(n); for (var p = 0; p < n; p++) { if (!dict.ContainsKey(data[p])) dict[data[p]] = new List<int>(n); dict[data[p]].Add(p); } return dict; }
MinhThai2 Thank you for the tip for managing duplicate. I constructed a bucket list from cost to indices, combined with binary search, and was able to finally solved the last failed test case.
Priyesh_coder Binary search is log(n)
ynerush Binary search is logn, but sorting is nlogn;
akrox58 Right! Sorry!
samrath But if we do binary search, before that we have to sort it and in that case the index of the numbers were changed and finally we have to return the index not the number.
hg3994 Input the values in an array a[] Make a temporary array with it temp[] O(n) Do all the operations in temp[] after which you would know which 2 elements form the sum. O(n*logn) After that just search for those element's index in the a[] array in O(n) time.
Final Complexity= O(n*logn)
smartsammy787 How is this solution going to solve the problem of duplicate prices of ice cream?
Ravindhart [deleted]Ravindhart Duplicates are not a concern here as we have to look for two distinct indices(i.e. flavors) whose sum yeilds the target(M).
abitdodgy How are duplicates not a concern? If you have an array of
[1, 2, 5, 2]and the sum is 4, then answer answer indexes are1and 4. When you search for the elements, you will always find the first element, and end up returning1and1instead. In otherwords, the index of the first occurence of one of the answers.heinzquadrat That is correct -- but you can perform two linear searches and throw out the first hit of the second search if and when it matches the result of the first search. Alternatively, one may search from back to front.
Since the original order is to be kept, I am unaware of alternatives to linear search. By using the two-pointer technique, I arrive at O(nlogn + n + n) = O(nlogn).
abitdodgy I tried that already, but some test cases are failing.
pairis an array of the values whose indexes we need for the answer (not important, but obtained through a binary search on a sorted version of the array).This code iterates over each value in
pair, left value first. For each value, it executes a linear search on the original, unsorted flavours array. Once it locates the value, it prints the current index and sets the value tofalseso that when looking for the second value, if it's a duplicate, it will not fund the first occurence (it will befalse, at this stage). We then break the loop because we no longer need to do anything more on the current loop.I can't see why some test cases are failing, though. Ideas?
pair.each do |value| for i in 0...flavours.size if flavours[i] == value print "#{i + 1} " flavours[i] = false break end end end print "\n"
heinzquadrat I don't know the first thing about ruby, but I would:
. try a value other than "false", like -1
. just to be absolutely sure, do a search from right to left
abitdodgy That won't make a difference because this will never be true:
Integer == false. If a value is not found in the binary search, it will come back asnil. I also tried searching from right to left, and the same cases are failing. I wonder if my binary search algorithm is what's failing? It's really frustrating not to have access to the test cases. It's rediculous, in fact. Under what circumstances will anyone be debugning without access to the data?yatesyates I agree with you about the problem of duplicates and I think that makes using arrays with binary search a poor approach. Of course I coded the whole array based solution before realizing this.
I think the better solution is to create a binary search tree as you read the costs in. Each node in the tree has the original index and the cost. Every time you read a new cost from stdin, first search the tree to see if it's matching pair is already there. If it's not, then insert it to the tree.
shuhua_gao I guess the node should store all the indices for duplicated costs. For example, [1, 2, 5, 2], then the node corresponding to the cost 2 should store indices 2 and 4. In this way, the duplication puzzle is handled.
Well, in C++, we can use std::multimap to achieve this.
JDenman6 I think 'break' breaks out of the each loop, so it won't search for the second item. I think you should use 'next' there instead.
loren2m The question states that there will be only one correct solution for each day, so this should not occur.
b_hus_han exactly
padalkars But in the worst case, inserting all the elements in a BST could take O(n^2) time. In the worst case the tree is right skewed, or left skewed. We would require to balance the tree in order to get a O(log n) time.
premkagrani binary search is logn not nlogn.
nikhiltulseja Thanks a lot !
eduardocesar A simple solution O(nlongn):
Sort the array and save 2 postions (min = 0 and max = size -1) and change this postions(min ++ and max --) until the sum is equal to M. The problem in this method is the necessity to save a copy from initial array to find the index to print them. (Memory usually is not problem in this chalange)
pmalek What if you have an array
1 2 3 4 5and the sum is5? You will not find a solution (which is there) with this method.
themadpr0gramer 1 4 technically comes before 2 3.
Therefore it's still correct.
pmalek But by the description I would unserstand it so that we parse:
1 5first, then2 4, then3 3?aknautiyal constraint says the solution is unique for a given test.
acs2010 Actually, in one step with EITHER do min++ OR do max --, but not both.
Bad_Jim You move the left index if the total cost is less than your budget and the right index if it is too much.
1 2 3 4 5
Start with l=1, r=5. That's 6, which is too much. We therefore move the right pointer to 4, and discover a solution.
I used this method, and I passed.
dude_mil How will it work if the values are 1 1 5 2 2 ? if the right pointer moved one index down, it will never find the solution (2, 2)
Bad_Jim I was replying to pmalek, who was replying to Eduardocesar, who suggested sorting the array first.
dude_mil Oh ok, my bad. I just wonder, even if the array is sorted what logic shoule be used to move indexes.. for example [0 2 3 4 5 6], how do I get to 2, 5 for 7 AND 0, 4 for 4
Bad_Jim You move the left index if the total cost is less than your budget and the right index if it is too much.
[0,2,3,4,5,6] Initially pointing at 0 and 6
With a target of 7, we note that 0+6=6, which is less than 7, so we move the left pointer to 2. 2+6=8 is more than 7, so we move the right pointer and get 2+5=7
With a target of 4, we see that 0+6=6, which is more than 4 so we move the right pointer. 0+5=5, which is also more than 4 so we move the right pointer again and discover the answer.
dude_mil Got it, thank you so much for the explanation.
ruchika Nicely explained.
NiceBuddy or you can store only the values which are needed to be deal with, also along with its index and then find the difference, which may be much easier: something like this:
#include <vector> #include <map> #include <iostream> using namespace std; #define ul unsigned long int int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); ul T; cin >> T; for (auto t = 0; t < T; ++t) { ul m = 0, n = 0; multimap<ul, ul> myMap; vector<ul> vecValues; cin >> m >> n; for (auto idx = 1; idx <= n; ++idx) { ul tempFirst = 0; cin >> tempFirst; if (tempFirst <= m) { myMap.emplace(tempFirst, idx); vecValues.push_back(tempFirst); } } for (auto &vec:vecValues) { multimap<ul, ul>::const_iterator current = myMap.find(vec); ul curr_value = current->first; ul id = current->second; ul diff = m - curr_value; myMap.erase(current); multimap<ul, ul>::const_iterator gett_id2 = myMap.find(diff); if ((gett_id2 != myMap.cend()) && (gett_id2->first + curr_value == m)) { cout << id << " " << gett_id2->second << endl; break; } } } return 0; }
NiceBuddy [deleted]
Sonia05 how can we get the index of old array from sorted array?
Bad_Jim Store each price/index pair in a struct, class or tuple and sort those by price.
AffineStructure Hey Jim, I read your solution. Can you explain your for loop with skip? I didn't really understand what you were doing there.
d7047022 [deleted]
janusz_k O(n) with map
public static void main(String[] args) { try (Scanner scanner = new Scanner(System.in)) { int numberOfTestCases = scanner.nextInt(); for (int i = 0; i < numberOfTestCases; i++) { buyIcecream(scanner); } } } private static void buyIcecream(Scanner scanner) { int m = scanner.nextInt(); int n = scanner.nextInt(); ArrayList<Integer> costTable = new ArrayList<>(); for (int i = 0; i < n; i++) { int price = scanner.nextInt(); costTable.add(price); } Map<Integer, List<Integer>> positionMap = new HashMap<>(); for (int i = 0; i < costTable.size(); i++) { Integer price = costTable.get(i); positionMap.putIfAbsent(price, new ArrayList<>()); positionMap.get(price).add(i); } int lower = 0; int higher = 0; int slider = 0; boolean found = false; while (slider < costTable.size() && !found) { int leftvalue = costTable.get(slider); int lookup = m - leftvalue; List<Integer> positions = positionMap.get(lookup); if (positions != null) { Integer max = Collections.max(positions); if (slider < max) { found = true; lower = slider; higher = max; } } slider++; } System.out.printf("%d %d%n", lower + 1, higher + 1); }
b0kater Not better than O(n), but you can still get more efficient. You can build and use a map in a single pass.
for(int i=0;i<trips;i++) { int money = scan.nextInt(); int flavors = scan.nextInt(); int[] prices = new int[flavors]; for (int j=0;j<flavors;j++) { prices[j] = scan.nextInt(); } HashMap<Integer, Integer> possibleSolutions = new HashMap<Integer, Integer>(flavors/2); // Key = price that will solve the problem, Value = the flavor id (base 0) having money-neededPrice for (int k=0;k<flavors;k++) { if (prices[k]<money) { if (possibleSolutions.containsKey(prices[k])) { // solution found System.out.println((possibleSolutions.get(prices[k])+1)+" "+(k+1)); break; } else { // add as possible solution possibleSolutions.put(money-prices[k], k); } } } }
DanYoo940 Simple
public static void main(String[] args){ Scanner scan = new Scanner(System.in); int tryNumber = scan.nextInt(); for(int z = 0;z<tryNumber;z++){ int money = scan.nextInt(); int options = scan.nextInt(); List list = new ArrayList<Integer>(); for(int i =0; i<options;i++){ list.add(scan.nextInt()); } for(int i =0; i<list.size();i++){ for(int ii=i+1;ii<list.size();ii++){ if(money==(int)list.get(i)+(int)list.get(ii)){ System.out.println((i+1)+" "+(ii+1)); break; } } } }
Smooth_AF public class Solution { static void quickSort(int[] arr, int hi, int lo){ if(lo<hi){ int pi = partition(arr,lo,hi); quickSort(arr,lo,pi-1); quickSort(arr,pi+1,hi); } } static int partition(int[] arr,int lo,int hi){ int pivot = arr[hi]; int i = lo-1; for(int j=lo; j<hi; j++){ if(arr[j]<=pivot){ i++; int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; } } int temp = arr[i+1]; arr[i+1] = arr[hi]; arr[hi] = temp; return i+1; } public static void main(String[] args) { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); //total number of testcases for(int x=0;x<t;x++){ int m = scan.nextInt(); //total money available int n = scan.nextInt(); //total varieties of ice-cream int[] arr = new int[n]; //array of prices for(int i=0;i<n;i++){ arr[i] = scan.nextInt(); } int sum, min_sum = 999999; int l=0,r=n-1; int min_l = l, min_r = r; quickSort(arr,l,r); while(l<r){ sum = arr[l] +arr[r]; if(Math.abs(sum) < Math.abs(min_sum)) { min_sum = sum; min_l = l; min_r = r; } if(sum==m) break; else if(sum<m) l++; else r--; } System.out.println((min_l+1)+" "+(min_r+1)); } } }
Smooth_AF is there any problem with the approach? O(nlogn) complexity, but pass only the second test case and not the first!
Bad_Jim Well first off it seems that your sort function does nothing. If I add a bit of code to print out the array after sorting like this:
quickSort(arr,l,r); for(int i=0; i<n; i++){ System.out.print(arr[i]); System.out.print(' '); } System.out.println();
It prints out the same array as the input. Try the built in sort function:
Arrays.sort(arr);
Bad_Jim The other big problem is that you have to print the original positions of the two ice creams you find, and sorting destroys this information.
There are a couple of ways to solve this problem. One way to do it is to make a copy of the original array before sorting it. You can then look through the old array for the prices you found.
The other way is to make an ice_cream class that holds the price and original index of an ice cream. You can then sort the ice creams, find a pair with the required combined price and then you will also know their original indices. To do this you will need to tell the sort function how to compare ice creams, which is done by implementing the Comparable interface and overriding compareTo(). Here's the code you need to do this:
/* most guides just write "implements Comparable", but then you have to write code to handle any kind of Object. The <ice_cream> bit means you are only showing how to compare with other ice creams. */ class ice_cream implements Comparable<ice_cream>{ public int price; public int original_index; // constructor public ice_cream(int p, int oi){ price = p; original_index = oi; } /* CompareTo should return -1,0 or 1 depending on whether the object is less than, equal or greater than the other object by whatever criteria you have defined @Override generates a compile time error if the method does not override another method. It is not necessary but is good style. */ @Override public int compareTo(ice_cream other){ if (this.price < other.price){ return -1; }else if(this.price > other.price){ return 1; }else return 0; } // Lets you print it out @Override public String toString(){ return "(" + price + ", " + original_index + ") "; } };
Technically, I think it is actually better to make a copy before sorting. You add a couple of O(n) operations by doing this, while using objects instead of plain integers makes the O(nlogn) sorting operation slower. However, I think you learn more with the second approach, so I encourage you to try it out.
AseemYadav It kind of works the same way (if I am not wrong) , as that of the sorting algorithm of zeroes and ones in an array.
strudeau @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).
alexjst You can't use just a 'standard' hashtable that simply stores the prices, since you generally cannot figure out the corresponding index that you need to output. You would either need a hashmap to store the index along with the price, or you may use an array of length M instead of the hashmap: when scanning C(i), you store the index number i into the (M-C(i))'th element of the array. That way you can always directly figure out the index from a given price later during the scan.
puneetjain1891 But how would you manage duplicates indexes in array?
puneetjain1891 sorry, there is only one possiblity when dupicates need to be stored is that if M/2 is present two times in list otherwise we don't need to store any dupulicates with higher index becasue M/2 + M/2 = M.
caiyo I used a HashMap where the the key is the price and the value is the index and I only hold the higher index in the hashmap. When searching the hashmap for the leftover value (M-price[i]), if the value saved in the hashmap != i, then that is the answer. Remember that each test case has a unique answer so there would only be at most 2x M/2 prices if it is the answer
jag95 How do you deal with duplicate prices? You can't have duplicate keys in a HashMap.
shuhua_gao This is why we use std::multimap. For example,two pairs like <1, 'a'> and <1, 'b'>, then they will be stored together. When you retrieve the key 1, you will get two values 'a' and 'b'.
I guess there are similar structures in other languages. Even if there is none, you can handcraft one. For example, the value type is a dynamic array D. When you add a new pair, first check whether the key is existent already. If it is existent, then retrieve its corresponding value D and append the value to D.
pocomaxa If the duplicate is not the answer, then it won't matter if you overwrite the value in the map.
id_prefer_not_to you can use a standard hashtable, where the key is an integer (M - array[i]) and the value is the integer index i. then as you go through the array, you check if (array[current_index]) is in the table; if it is, then the value in that slot is the index i for which M - array[i] = array[current_index] and that is the solution.
abitdodgy This doesn't seem to work with duplicate values... this fails the third test.
t.times do cash = gets.to_i number_of_flavours = gets.to_i flavours = gets.chomp.strip.split(' ').map(&:to_i) hash = Hash[flavours.map.with_index { |e, i| [e, i] }] flavours.each.with_index do |e, i| if i2 = hash[cash - e] puts "#{i + 1} #{i2 + 1}" break end end end
snhusnu They cannot buy the same elemnt in the same index. You need to check whether i+1 == i2+1, if they equal, you cannot break the loop.
AffineStructure Here is my Python3 solution that uses HashMap
### LIBRARIES ### from collections import defaultdict ### INPUTS ### Trips = int(input()) ### FUNCTIONS ### def IceCream(index, dollar, data): for i in data: #If the values are heterogeneous, then we return the sorted indexes. if (dollar - i) in data and (i != dollar - i): return sorted([data[i][0],data[dollar-i][0]]) #If the values are homogeneous, we make sure there is more than one instance. elif(dollar - i) in data and (i == dollar - i): if len(data[i]) > 1: return sorted([data[i][0],data[i][1]]) else: continue else: continue ### OUTPUTS ### for _ in range(Trips): dollar = int(input()) index = int(input()) inputData = [int(i) for i in input().split()] #Initializing list objects, where the offset indexes will live. data = defaultdict(list) #enumerate returns the index and the value, here as i,j; respectively. for i,j in enumerate(inputData): data[j].append(i+1) #* unpacks the arguments. print(*IceCream(index, dollar, data))
vishalg2235 following code shows terminated due to timeout!!! plzz help i didnt understand what I'am doing wrong.
t = int(input().strip()) m = [] n = [] cost = [] index = [] flag = 0 for i in range(t): m.append(int(input().strip())) n.append(int(input().strip())) cost.append([int(i) for i in input().split()]) for i in range(t): flag = 0 for k in range(n[i]): for l in range(n[i]): if cost[i][k] + cost[i][l] == m[i] and k!=l and flag==0: index.append([k+1,l+1]) flag = 1 for item in index: print(*item, sep=' ')
abhiramsatpute this code has time complexity of O(n^3) which is much more than max limit
AghalarovBahruz for item in index: print(*item, sep=' ')
this one you can replace with
print(*index)
dwongep [deleted]
jamesw129 Why bother optimizing when there is no need? This problem does not have any test cases with large number of inputs. KISS
phderome number of flavours could reach 10000 and so n log n versus n^2 does make a difference. But personally I didn't feel compelled to optimize from n^2 either.
apolo4pena Agreed. If its not broken don't fix it. Be a good lazy programmer.
kanha001 thats exactly my approach to this problem. I solved it just few mins ago. good to see some one else also thought of such a approach
aa1992HackerRank Admin 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.
ynerush [deleted]
RalphD What exactly do you mean by "Initializing an array with -1"? Do you mean
arr[0] = -1? Or perhapsfor (int i = 0; i < c.length; i++) arr[i] = -1?Also, since
M - arr[i]is not an index I wouldn't know why to check if that is bigger than 0. Perhaps you meant that we should find the index ofarrsuch thatarr[index] = M - arr[i] && index >= 0whereiis your loop iterator.It seems to me like this algorithm is O(n^2) though. You iterate over
arrwith loop iteratoriand then iterate overarragain with loop iteratorindex.What are my misunderstandings here?
Pvokd i did it without sorting the array, just put a loop finding pairs whoose sum is equal to m.
airwindh you can also solve it using two pointer algorithm..
vivekvpandya @airwindh, Is it like maintaining 2 values and change one if next value takes the sum closer to the answer ?
ennorehling I believe you're using a funny name for what's commonly known as binary search.
piyus 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)); } } } }}
somananda good job,, but your solution is not a quicker one
piyus Can u please let me know of the other approach , could improve myself.
somananda every time when we have enter an array,we have to ckeck whether the sum of that array with each array we already entered or exist is equal to m(M dollars) .if it is then we have to print the index +1 (your one is bit similar to mine but this one is much faster)(below one is two pointer method,which is much faster)
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'); } return 0;}
piyus I cant understand how urs is faster than mine , u have a while loop inside for , while i just have a single for loop ?
somananda its because of stored in non consecutive index of array in your program,which might take much longer time then normal arrray
Meenachinmay right bro.....
devmilind17 [deleted]
oconnorct1 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.
kostian_igor As a small perfomance tweak, you can exclude items >= (m) from calculating, because they will never have a pair.
indra_malav 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; }
abhishek_falmari Great one.
nishakhiyani Your code is so simple to understand. Great one. Thanks. :)
ahmedsadman_211 Can you please explain how this works?
Bad_Jim I believe the idea is to use a hashmap. Given the index of an ice cream and it's price, you can retrieve the index of another ice cream (if it exists in the map) like this:
maps[price]and both ice creams will have a combined price of m, giving you the answer. The line:
if( maps.find(v[i]) != maps.end() ){looks a bit strange but it is actually just the standard way to check whether a key exists in a map. v[i] is the price he is checking.
Having unchecked the price of an ice cream in the map and found nothing, he then adds it to the map a bit like this:
maps[m - price] = index;so it can be found when checking ice creams further on.
There is one small flaw in the code, and that is the fact that he should use unordered_map instead of map. unordered_map would allow an solution because it uses hashmaps, but map uses a tree based implementation so his solution is really .
sreekeshav67 for(int z=1;z<=t;z++) { sum = s.nextInt(); n = s.nextInt(); int a[] = new int[n]; for(int i=0;i<n;i++) { a[i] = s.nextInt(); } for(int i=0;i<n-1;i++) { for(int j=i;j<n-1;j++) { if(a[i]+a[j+1]==sum) { System.out.println((i+1)+" "+(j+2)); } } }
prajjwal_sharma1 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)
sumitsainee7 void icecreamParlor(int m, int n, int* a, int *rs) { // Complete this function for(int i=0;i
conorliv I think my solution has O(n) time complexity and O(n) space complexity.
- Loop through costs and build up hash table to map cost to ice cream type
- 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])
sdewey Yes, this is the correct solution. I don't know why everybody else is choosing such complicated solutions.
BTW you don't even need your check that "the index is different than the current index" if you do a single loop (for checking and adding) and wait to add items to the dict after you have already checked whether "remaining" is in the dict. It's also faster because you only loop once.
Here is my solution:
def icecreamParlor(m, arr): seen = dict() for i, cost in enumerate(arr): if ((m - cost) in seen): ans = [seen[m - cost] + 1, i + 1] ans.sort() return ans seen[cost] = i
tat_lim 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; }
ganeshbg93 Simple solution in python:
no need to sort
t = raw_input() t = int(t) for i in range(0,t): m = raw_input() m = int(m) n = raw_input() n = int(n) li = raw_input() #list of elements from input li = [int(i) for i in li.split(' ')] for i in range(0,len(li)): if (m-li[i]) in li[i+1:len(li)]: #check if the difference of m and element in the list exist, if yes then pick the index of those two elements. li1 = li[i+1:len(li)] #if the same element appears twice, for example m=4 and the list has 2 2 4 1, this line helps in picking the next '2' at the position 1(starting from 0) x = li1.index(m-li[i]) #position of the next element which forms the sum equal to m. print i+1, i+x+2 #Since index starts from 0 add 1 to i, to print the second index, remember we have copied all the elements after position i, so i+x, since the index starts from 0, i+x+1, we left the element at position i while copying to li1, hence i+x+2 break
vshantam Splitting the list was a nice and different approach that you made and i liked it.
erich_kramer1 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)
nelson_matos Here is a Java solutions that runs in O(n)
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); for(int i = 0; i < n; i++){ int cost = scan.nextInt(); int size = scan.nextInt(); int prices[] = new int[size]; for(int j = 0; j < size; j++){ prices[j] = scan.nextInt(); } determineFlavors(prices,cost); } } public static void determineFlavors(int prices[], int maxCost){ HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); map.put(prices[0],1); for(int i = 1; i < prices.length; i++){ Integer k = map.get(maxCost - prices[i]); if(k == null){ map.put(prices[i], i+1); }else{ System.out.println(k + " " + (i+1)); break; } } }vineetsood5 Nice solution
vkgg3 This is not O(n) solution. It is O(n^2)
nelson_matos Yes, you are correct. I meant to say it is O(n) for each test case. If there are multiple test case for a problem it can be viewed as O(n^2).
Soul_XHacker 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.
rasik210 You were on the right path indeed. Dictionary can be used for solving this problem. @nelson_matos solution is certainly of order n but precisely it is O(2n) as he is running two for loops one after the other which is not required. Here is how you can do it in single iteration which results in O(n) complexity precisely. In fact, if the desired pair is found mid-way then you don't have to even iterate the entire array:
I started iterating the array elements. I created a dictionary look up (element,index) of the input array as I iterated through the elements. e.g. for the input test case # 0
4 (Sum to be found) 5 (number of input elements) 1 4 5 3 2I created a look-up data structure as shown below for each value and its index in the array during iteration:
1 - 0 4 - [value >= 4. So ignored as a pair will not be possible in this case] 5 - [value >= 4. So ignored as a pair will not be possible in this case] 3 - [Solution found at this element. Break further iteration]Case # 1 has got duplicate elements. So how do you insert the duplicate values in dictionary?
4 (Sum to be found) 4 (number of input elements) 2 2 4 3Duplicate value will have two cases:
- Either it will be part of the solution pair. So, you will get solution the moment you reach to the duplicate element. So you will not need to insert it any way.
If it is not part of the solution pair then you can simply ignore it. Move to next element and continue iterating.
Time Complexity: O(n) //there are no nested for loops. Space Complexity: O(n) //an extra look-up dictionary storage is required
Here is my complete C# solution.
AlexL70 Preliminary test doesn't cover half of possible cases. To check it more o less well I would suggest next test case extension.
Input:
4
4
5
1 4 5 3 2
4
4
2 2 4 3
6
11
2 3 5 6 2 4 2 3 4 5 3
6
11
3 5 4 3 2 4 2 6 5 3 2Expected output:
1 4
1 2
1 6
3 5
It makes sure that you always take first two suitable numbers in a row and output their positions in proper order.
The next is
spoilersolution. Don'r read it if you like to do it yourself.
I did it by sorting dataset first by price, end then by index in original array and doing search moving towards the middle from opposit directions.
t_serban88 Why is the correct answer for the last case 3 5 (4 + 2) and not 1 4 (3 + 3)?
AlexL70 Hm... You are right. Obviously my implementation gives 3 5 (4 + 2) because I move from opposit directions through sorted array, so my algorithm first meets solution with most different numbers. Though, test case is not good enough cause it allows ambiguity. If you replace every "3" in last line by (lets say) "7", "3 5 (4 + 2)" would be still the right answer, and the only one.
my_account It seems that in C# the only way to read long string from standard input is this code:
Console.SetIn(new StreamReader(Console.OpenStandardInput(8192), Encoding.Default, false, 8192)); string s = Console.ReadLine();
It works locally, but for some reason s==null on test-server, so all long test-cases are failing.
rasik210 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?
Ajey01 Is anybody have better solution than this one!!! if yes, plzz reply with solution....
#!/bin/python3 import sys def icecreamParlor(m, a,n): d={} k=1 for i in a: s=m-i if s in d: return d[s],k else: d[i]=k k=k+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(' '))) result = icecreamParlor(m, arr,n) print (" ".join(map(str, result)))
alexermashev One question why this problem is related with binary search?
conormuldoonAsked to answer Endorsed by alexermashevIf 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.
hsdars Failing on test cases 2 and 3,couldnt find out any flaw in the code when i checked. Need help debugging it http://ideone.com/6EfVXf
hsdars Need help with this problem
usamakhaq I didn't keep the array sorted, but I kept on checking the inputs as they came in to see if there was a match, then I just ignored the rest.
int t = 0; cin >> t; for(int i = 0; i < t; ++i){ int m = 0, n =0; cin >> m; cin >> n; std::map<int,int> s; bool ignore = false; for(int j = 0; j < n; ++j){ int temp = 0; cin >> temp; if(!ignore){ if(temp < m){ if(s.find(m -temp)!=s.end()){ // if we find, let's print the indices, just ignore the rest of the input. // might make it more efficient. just a thought. cout << s[m-temp]+1 << " " << j+1 << endl; ignore = true; } else{ s[temp]=j; } } } } }shubham_marathia Is it accepted or a hypothesis you have proposed ?
If it is working maybe you could have broken the loop when ignore is true.
usamakhaq Not sure if it is accepted, but I came to the conclusion after thinking about it. I can not break out of the loop because there are still incoming values in the stream, I don't want to roll those over to the next test case. Basically look at it this way, if your sum is 5 and your array is: 1 4 3 2 I know after 1 and 4 I have my answers, but if I don't do cin for 3 and 2, then breaking out will just take them to the next case.
andreialexandru python3:
def icecreamParlor(m, arr): mylist = [] for i in range(len(arr)): for j in range(len(arr)): if ( arr[i] + arr[j] ) == m and i < j: mylist.append(i+1) mylist.append(j+1) mylist.sort() return mylist
Sort 380 Discussions, By:
Please Login in order to post a comment