Re: [algogeeks] Re: sum of two
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 scenario ?
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
On Sat, May 28, 2011 at 10:47 AM, Aakash Johari aakashj@gmail.comwrote:
@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 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/
group/algogeeks/msg/541180b4f2d6c930) using map doesn't satisfy the
time requirement.
Dave
On May 27, 3:38 am, anshu mishra anshumishra6...@gmail.com wrote:
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
@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 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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
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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the
Re: [algogeeks] Re: sum of two
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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
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, sukhmeet singh sukhmeet2...@gmail.comwrote:
@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 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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
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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
You received this message because you are subscribed to the
Re: [algogeeks] Re: sum of two
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 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, sukhmeet singh sukhmeet2...@gmail.comwrote:
@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 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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
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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more
Re: [algogeeks] Re: sum of two
@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, 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 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, sukhmeet singh
sukhmeet2...@gmail.comwrote:
@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 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out
two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google
Groups
Re: [algogeeks] Re: sum of two
@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 of array without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
@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, 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 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, sukhmeet singh
sukhmeet2...@gmail.comwrote:
@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 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out
two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the
Re: [algogeeks] Re: sum of two
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 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 of array without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh sukhmeet2...@gmail.comwrote:
@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, 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 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, sukhmeet singh sukhmeet2...@gmail.com
wrote:
@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 Fri, May 20, 2011 at 8:01 AM, Dave dave_and_da...@juno.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com
wrote:
given an array of integers, and an integer k, find out
two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
Re: [algogeeks] Re: sum of two
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 be avoided
On Fri, May 27, 2011 at 2:32 PM, bhavana bhavana@gmail.com wrote:
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 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 of array without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh
sukhmeet2...@gmail.comwrote:
@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, 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 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, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.com
wrote:
@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.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com
wrote:
given an array of integers, and an integer k, find out
two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact
Re: [algogeeks] Re: sum of two
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 '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 be avoided
On Fri, May 27, 2011 at 2:32 PM, bhavana bhavana@gmail.com wrote:
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 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 of array without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh
sukhmeet2...@gmail.comwrote:
@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, 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 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, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.com wrote:
@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.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com
wrote:
given an array of integers, and an integer k, find
out two
elements
from the array whose sum is k in O(n) time. if no
such element
exists
output none.
--
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 email to
Re: [algogeeks] Re: sum of two
@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 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
'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 be avoided
On Fri, May 27, 2011 at 2:32 PM, bhavana bhavana@gmail.com wrote:
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 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 of array
without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh sukhmeet2...@gmail.com
wrote:
@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.comwrote:
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.com
wrote:
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, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.com wrote:
@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.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com
wrote:
given an array of integers, and an integer k, find
out two
elements
from the array whose sum is k in O(n) time. if no
such element
exists
output none.
--
You received this message because you are subscribed
to the Google
Groups
Re: [algogeeks] Re: sum of two
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, 16, 25, ..., n^2?
On Fri, May 27, 2011 at 2:44 PM, Aakash Johari aakashj@gmail.comwrote:
@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 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
'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 be avoided
On Fri, May 27, 2011 at 2:32 PM, bhavana bhavana@gmail.com wrote:
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 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 of array
without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.comwrote:
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.com wrote:
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, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.com wrote:
@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.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
Re: [algogeeks] Re: sum of two
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 sukhmeet2...@gmail.comwrote:
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, 16, 25, ..., n^2?
On Fri, May 27, 2011 at 2:44 PM, Aakash Johari aakashj@gmail.comwrote:
@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 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
'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 be avoided
On Fri, May 27, 2011 at 2:32 PM, bhavana bhavana@gmail.com wrote:
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.comwrote:
@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 of array
without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.comwrote:
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.com wrote:
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, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.com wrote:
@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.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com
wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 or
else
decrement j.
Re: [algogeeks] Re: sum of two
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 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 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 of array without
entering the if condition the array doesnt contain any such pair.
On Fri, May 27, 2011 at 2:26 PM, sukhmeet singh
sukhmeet2...@gmail.comwrote:
@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, 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 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, sukhmeet singh
sukhmeet2...@gmail.com wrote:
@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.com
wrote:
@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.comwrote:
@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, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com
wrote:
given an array of integers, and an integer k, find out
two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
You received this message because you are subscribed to the
[algogeeks] Re: sum of two
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/ group/algogeeks/msg/541180b4f2d6c930) using map doesn't satisfy the time requirement. Dave On May 27, 3:38 am, anshu mishra anshumishra6...@gmail.com wrote: 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
@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 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/ group/algogeeks/msg/541180b4f2d6c930) using map doesn't satisfy the time requirement. Dave On May 27, 3:38 am, anshu mishra anshumishra6...@gmail.com wrote: 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- -Aakash Johari (IIIT Allahabad) -- 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
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 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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
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 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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@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 amitthecoo...@gmail.com wrote: given an array of integers, and an integer k, find out two elements from the array whose sum is k in O(n) time. if no such element exists output none. -- 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@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;
for ( i = 0; i 10; i++ ) {
m[a[i]] = 1;
}
sum = 13;
for ( i = 0; i 10; i++ ) {
if ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
@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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@ 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 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 amitthecoo...@gmail.com wrote: given an array of integers, and an integer k, find out two elements from the array whose sum is k in O(n) time. if no such element exists output none. -- 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@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: @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 amitthecoo...@gmail.com wrote: given an array of integers, and an integer k, find out two elements from the array whose sum is k in O(n) time. if no such element exists output none. -- 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 email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@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 value of the entry? For example, is it O(n) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@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, SVIX saivivekh.swaminat...@gmail.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 value of the entry? For example, is it O(n) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
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
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, SVIX saivivekh.swaminat...@gmail.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 value of the entry? For example, is it O(n) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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
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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
Re: [algogeeks] Re: sum of two
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 to k then stop else move untill j i.
I think this solution will have O(n) time complexity and O(n space
complexity).
On Fri, May 20, 2011 at 7:22 PM, Aakash Johari aakashj@gmail.comwrote:
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 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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two elements
from the array whose sum is k in O(n) time. if no such element exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
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 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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
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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sum of two
@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 say???
On Fri, May 20, 2011 at 8:31 PM, 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group
Re: [algogeeks] Re: sum of two
@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
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 say???
On Fri, May 20, 2011 at 8:31 PM, 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) to map the sequence
1, 4, 9, 16, 25, ..., n^2?
Dave
On May 20, 9:39 am, Aakash Johari aakashj@gmail.com wrote:
@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 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 ( m[sum - a[i]] == 1 ) {
flag = 1;
break;
}
}
if ( flag == 1 )
cout a[i] sum - a[i] endl;
return 0;
}
On Fri, May 20, 2011 at 7:01 AM, 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
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 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 nos
sum=a[i]+a[j];
if (sum==k)
{
b[p++]=i;b[p++]=j;
}
elseif(sumk)
i++;
else(sumk)
j++;
return b;
}
On May 20, 4:38 am, amit amitthecoo...@gmail.com wrote:
given an array of integers, and an integer k, find out
two
elements
from the array whose sum is k in O(n) time. if no such
element
exists
output none.
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Gunjan Sharma
B.Tech IV year CSE
Contact No- +91 9997767077
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)- Hide quoted text -
- Show quoted text -
--
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 email to
algogeeks+unsubscr...@googlegroups.com.
For more
