Author |
Topic: Maximum sum of 2 array elements (Read 825 times) |
|
mad
Junior Member
Posts: 118
|
 |
Maximum sum of 2 array elements
« on: Feb 6th, 2008, 10:14pm » |
 Quote  Modify
|
Q.1)S contains the set of positive integer.Find the largest number c such that c=a+b where a,b,c are distict numbers in the set.
Q.2)write the program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.
Sorry if this has been posted before. Please provide the link in that case.
|
| « Last Edit: Feb 6th, 2008, 10:20pm by mad » |
 IP Logged |
|
|
|
d33p4k
Newbie
Posts: 12
|
|
Re: Maximum sum of 2 array elements
« Reply #1 on: Feb 11th, 2008, 10:30am » |
Quote Modify
|
1.
Brute force approach will take O(n3) time.
But it can also be solved in O(n2) time and O(n) space:
First, sort the list and make a copy of it. Then, starting with the first element( call it 'a'), subtract the element value from each of the remaining elements of the second list. Now, there are two sorted list. And greatest common element( call it b) between them can be found in O(n) time. This element when added with 'a' gives the greatest common element (call it c) for that 'a'. Repeat this process for all elements in the list and the greatest among all c's is the answer.
If preserving the order of the elements is not required, then it can solved in O(n2) time and in space.
Sort the elements. Now, start with the last element( call it ak), find the first two consecutive number ai and aj in the list, such that ai + aj >= ak, and j= i +1.
a1....ai-1 ai...aj aj+1...ak..an
if ai+ aj = ak, then return ak .
else
if ai-1+ aj < ak
j++;
if aj+1+ ai > ak
i--;
It can be easily proved that atleast one of the above two condition is always true. Thus, at each step atleast one element is discarded. Total time it would take is O(k) time.
In order to get the final answer this has to be done for all k's from k=n to 1. So, overall complexity becomes O(n2).
2.
This can be solved in O(n) time and O(n) space.
| hidden: | | Make a suffix tree out of the file and find the 10 deepest forks in it. |
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender: 
Posts: 155
|
|
Re: Maximum sum of 2 array elements
« Reply #2 on: Feb 11th, 2008, 11:33pm » |
Quote Modify
|
@47
Why it is in O(n2)?
It can be done in O(n log n), as sorting takes that much time. And after it, do O(n) searching with two pointer technique.
Any doubt, welcome....
|
|
IP Logged |
|
|
|
d33p4k
Newbie
Posts: 12
|
|
Re: Maximum sum of 2 array elements
« Reply #3 on: Feb 12th, 2008, 12:21am » |
Quote Modify
|
on Feb 11th, 2008, 11:33pm, johny_cage wrote:@47
Why it is in O(n2)?
It can be done in O(n log n), as sorting takes that much time. And after it, do O(n) searching with two pointer technique.
Any doubt, welcome.... |
|
The second step needs to be performed for each element present in the list. That makes it O(n2) time algo..
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Maximum sum of 2 array elements
« Reply #4 on: Feb 12th, 2008, 1:04am » |
Quote Modify
|
Ohhhhh!!!!! 
i just take the question otherwise.....
yups u r right.... 
|
|
IP Logged |
|
|
|
kvs007
Newbie
Gender:
Posts: 18
|
|
Re: Maximum sum of 2 array elements
« Reply #5 on: Mar 7th, 2008, 11:41pm » |
Quote Modify
|
To get the top ten words in the file you can implement a hashmap with the keys as hashcode of words and value their count. then get the top ten counts from the hashmap. It will take O(n)
|
|
IP Logged |
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: Maximum sum of 2 array elements
« Reply #6 on: Mar 8th, 2008, 4:39pm » |
Quote Modify
|
q)Given an array of non negative integers and an integer k, you are required to device an O(n) time algorithm to find out if there exists at least one pair of integers, say i and j, in the given array such that i+j equals k. That is, you are required to return a boolean value.The array is not sorted.
|
|
IP Logged |
|
|
|
m_aakash
Junior Member
Posts: 96
|
|
Re: Maximum sum of 2 array elements
« Reply #7 on: Mar 8th, 2008, 4:45pm » |
Quote Modify
|
on Mar 8th, 2008, 4:39pm, mad wrote:| q)Given an array of non negative integers and an integer k, you are required to device an O(n) time algorithm to find out if there exists at least one pair of integers, say i and j, in the given array such that i+j equals k. That is, you are required to return a boolean value.The array is not sorted. |
|
Using hashtable we can get O(n) expected time. Is it possible to get O(n) worst case time if elements are arbitrary?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print