Could you please explain a dry run.
Lets say you have a list of element arr[] = {5, 3, 10, 9, 8, 23, 11, 4,13,
6, -1}.
On fly we took user input and the user enters 12 .
This can be formed of 12( one example like (13, -1) , (10, 3, -1) )
Could you please educate me how ur algo gona work on this
@Dave nd @Akash can u explain a bit more.. I didn't get what u say..
Inserting in a map takes O(log n) time !!
On Fri, May 20, 2011 at 8:35 PM, Aakash Johari aakashj@gmail.comwrote:
@Dave: This is what is still a doubt to me. I have searched but couldn't
get the info regarding this.
On
map is internally implemented with balanced binary tree and inserting in a
BST is o(logn);
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send
yes, you are right. map insertion takes O(log n) time. so if you know the
upper bound of N, you can simply map the existence/non-existence of any
particular element in an array. that will be in constant time (for query
purposes) and O(n) time for preprocessing.
On Fri, May 27, 2011 at 1:29 AM,
can be solved easily if the elements of the array lie in a limited range
which can b known beforehand...!!
On Fri, May 27, 2011 at 2:10 PM, Aakash Johari aakashj@gmail.comwrote:
yes, you are right. map insertion takes O(log n) time. so if you know the
upper bound of N, you can simply map
@bhavana : Explain..!!
as far as i get you is that it would be same as implementing map ...!!
isn't ??
On Fri, May 27, 2011 at 2:16 PM, bhavana bhavana@gmail.com wrote:
can be solved easily if the elements of the array lie in a limited range
which can b known beforehand...!!
On Fri,
@sukhi : instead of using a map...use a boolean array elements of whoch r
initialised to false.
Starting frm the first element of the arrayif the number n is greater
than k ignore itelse mark a[n]=true and check if a[k-n]==true then we
get the required result .bt if we reach the end
hey...bt this one works only in case given that the elements of the array
are non-negative.
On Fri, May 27, 2011 at 2:30 PM, bhavana bhavana@gmail.com wrote:
@sukhi : instead of using a map...use a boolean array elements of whoch r
initialised to false.
Starting frm the first element of
k.. got it .. but it was same as putting them into a map ..if the bound 'b'
is not known.. as said be Akash ..
But if STL is not allowed your approach is mch better..Noogle..
also a simple change that can be done if the each number is that we can
check if (sum - a[i] )!= i then getting same can
hehe...d difference is regarding time complexity...bcoz map takes 0(logN)
for insertion while array can b accessed in constant time through index.
On Fri, May 27, 2011 at 2:39 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
k.. got it .. but it was same as putting them into a map ..if the bound
@sukhmeet: could you get my approach? it was same as Bhavana explained.
On Fri, May 27, 2011 at 2:12 AM, bhavana bhavana@gmail.com wrote:
hehe...d difference is regarding time complexity...bcoz map takes 0(logN)
for insertion while array can b accessed in constant time through index.
On
actly i did.. but bhavana didn;t used STL ..!!
My question to you was regarding Dave 's query which i didn't understand
what he meant by saying : @Aakash: And tell me how map works. Is making an
entry O(1) regardless
of the value of the entry? For example, is it O(n) to map the sequence
1, 4, 9,
In the second approach I wrote to use array for mapping
you can simply map the existence/non-existence of any particular element
in an array. that will be in constant time (for query purposes) and O(n)
time for preprocessing.
On Fri, May 27, 2011 at 2:18 AM, sukhmeet singh
ya .. it can work for negative indexes also if the bound is known.. like if
the range is from -10 to +10 then declare an array of 20 and then refer
a[10] as a[0] and use negative indexes to do the same procedure !!
On Fri, May 27, 2011 at 2:32 PM, bhavana bhavana@gmail.com wrote:
hey...bt
If map insertion is O(log n), then the algorithms that insert each
element into the map will be O(n log n), but the problem statement
insists that we find two elements of the array that sum to a given
number in O(n) time. Thus, Aakash's solution (http://groups.google.com/
@Dave: I have suggested another solution in previous threads. Please go
through that. That is without maps. It uses array for mapping.
On Fri, May 27, 2011 at 10:09 PM, Dave dave_and_da...@juno.com wrote:
If map insertion is O(log n), then the algorithms that insert each
element into the map
In while loop have i,j which points first and last index of array. In
while loop, Check the sum of a[i],a[j], If sumk,increment i or else
decrement j. Run the while loop till ij..
CODE:
int arraysum(int a[], int k, int i, int j)
while(ij)
{
int p=0;
int b[10]; //to store index of selected
First of all there is an infinite loop in this code
Secondly it works only for sorted array.
On Fri, May 20, 2011 at 7:16 PM, hari rajakin...@gmail.com wrote:
In while loop have i,j which points first and last index of array. In
while loop, Check the sum of a[i],a[j], If sumk,increment i
One possible solution is using maps. But i think that won't be in O(n)
On Fri, May 20, 2011 at 6:49 AM, Gunjan Sharma gunjan.khan...@gmail.comwrote:
First of all there is an infinite loop in this code
Secondly it works only for sorted array.
On Fri, May 20, 2011 at 7:16 PM, hari
makes it O(nlg(n))
On Fri, May 20, 2011 at 7:31 PM, hari rajakin...@gmail.com wrote:
We can sort using STL sort function in main() before function call of
arraysum().
On May 20, 6:49 am, Gunjan Sharma gunjan.khan...@gmail.com wrote:
First of all there is an infinite loop in this code
int main()
{
int a[10] = {5, 3, 10, 9, 8, 23, 11, 4, 12, 6};
int i;
int sum;
int flag = 0;
mapint, int m;
for ( i = 0; i 10; i++ ) {
m[a[i]] = 1;
}
sum = 13;
for ( i = 0; i 10; i++ ) {
if
We can sort using STL sort function in main() before function call of
arraysum().
On May 20, 6:49 am, Gunjan Sharma gunjan.khan...@gmail.com wrote:
First of all there is an infinite loop in this code
Secondly it works only for sorted array.
On Fri, May 20, 2011 at 7:16 PM, hari
@Amit: Use a hash table. For each integer x[i] in the array, search
for k - x[i]. If found, x[i] and k - x[i] are your pair of integers.
Otherwise, add x[i] to the hash table and advance the loop. Output
none if you get to the end of the array without a hit.
Dave
On May 20, 6:38 am, amit
@Aakash: Yeah, but try the same array with sum = 6 and see what
happens.
Dave
On May 20, 9:04 am, Aakash Johari aakashj@gmail.com wrote:
int main()
{
int a[10] = {5, 3, 10, 9, 8, 23, 11, 4, 12, 6};
int i;
int sum;
int flag = 0;
mapint, int m;
@Dave: I got you. I will have to check before pushing the element in map.
On Fri, May 20, 2011 at 7:30 AM, Dave dave_and_da...@juno.com wrote:
@Aakash: Yeah, but try the same array with sum = 6 and see what
happens.
Dave
On May 20, 9:04 am, Aakash Johari aakashj@gmail.com wrote:
int
@Dave: This is what is still a doubt to me. I have searched but couldn't get
the info regarding this.
On Fri, May 20, 2011 at 8:01 AM, Dave dave_and_da...@juno.com wrote:
@Aakash: And tell me how map works. Is making an entry O(1) regardless
of the value of the entry? For example, is it O(n)
@ I didn't get that... could u please elaborate a little more?
for each integer, search for something sounds like O(n^2)
On May 20, 7:26 am, Dave dave_and_da...@juno.com wrote:
@Amit: Use a hash table. For each integer x[i] in the array, search
for k - x[i]. If found, x[i] and k - x[i] are
@Dave.. never mind... i understood what u meant...
On May 20, 4:18 pm, SVIX saivivekh.swaminat...@gmail.com wrote:
@ I didn't get that... could u please elaborate a little more?
for each integer, search for something sounds like O(n^2)
On May 20, 7:26 am, Dave dave_and_da...@juno.com wrote:
@Dave... one more thought...
lets say the array is {1,2,3,6,6} (duplicate numbers) and u wanna
see if 2 numbers add up to 12 simple hashing wont work...
On May 20, 8:01 am, Dave dave_and_da...@juno.com wrote:
@Aakash: And tell me how map works. Is making an entry O(1) regardless
of the
@SVIX: Yes, simple hasing will work. After processing the first 4
numbers, the hash table contains 1, 2, 3, and 6. When you process the
second 6, you search for 12 - 6 = 6 and find it. The two numbers in
the array that sum to 12 are 6 and 6. What's the problem with that?
Dave
On May 20, 6:29 pm,
ah... u're right... dull moment... friday evening... not the first
dull moment today, i can assure u :)
On May 20, 4:39 pm, Dave dave_and_da...@juno.com wrote:
@SVIX: Yes, simple hasing will work. After processing the first 4
numbers, the hash table contains 1, 2, 3, and 6. When you process the
1. use radix sort and sort the array.
2. take two pointers(say i and j). Point the first to head and the second to
the tail of the array. then check for a[i] + a[j]. If this sum is greater
the decrement the pointer j else if the sum is less than k increment the i
pointer.
If you get the sum equal
A good example of trade-off space-time!
Somebody know the Speedup theoremhttp://en.wikipedia.org/wiki/Speedup_theorem?
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Fri, May 20, 2011 at 12:05 PM, Aakash Johari aakashj@gmail.comwrote:
@Dave: This is what is still a doubt to
@Apoorve: See my response at
http://groups.google.com/group/algogeeks/msg/72419fb69ce97774.
Dave
On May 20, 10:05 am, Apoorve Mohan apoorvemo...@gmail.com wrote:
@dave: i think this can be handled using a good hash function(an onto
function). then the space complexity will also be O(n). What
@Dave: He is talking of a better hash function. You did not mention the hash
function which you will use.
Anuj Agarwal
Engineering is the art of making what you want from things you can get.
On Sat, May 21, 2011 at 9:59 AM, Dave dave_and_da...@juno.com wrote:
@Apoorve: See my response at
35 matches
Mail list logo
