@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.
