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.com>wrote:
> 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 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.
>>
>
> --
> 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.
