Can work for negative also. Add a bias to each element.
On Fri, May 27, 2011 at 2:02 AM, 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 array....if the number n is greater
>> than k ignore it....else 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.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.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.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;
>>>>>>>> >
>>>>>>>> > > > map<int, 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
>>>>>>>> sum<k,increment i or
>>>>>>>> > > else
>>>>>>>> > > > > > > decrement j. Run the while loop till i<j..
>>>>>>>> >
>>>>>>>> > > > > > > CODE:
>>>>>>>> >
>>>>>>>> > > > > > > int arraysum(int a[], int k, int i, int j)
>>>>>>>> > > > > > > while(i<j)
>>>>>>>> > > > > > > {
>>>>>>>> > > > > > > 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(sum<k)
>>>>>>>> > > > > > > i++;
>>>>>>>> > > > > > > else(sum>k)
>>>>>>>> > > > > > > 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 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.
>>>>
>>>
>>> --
>>> 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.
>
--
-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.
