@ashish: yes it is given that elements are in 1-n range...
@anup: ur sol doesnt work for above case... try to make it general..
@abraham: i hv O(n2) sol, not required, that to of only 1st part...
guys try thinking 2nd part also....??
On Tue, Oct 4, 2011 at 8:14 AM, Ashish Goel <ashg...@gmail.com> wrote:
> 7 1 4 5 3 6 2
> try for
>
> is it necessary to have elements within 1-n range?
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Tue, Oct 4, 2011 at 7:36 AM, Anup Ghatage <ghat...@gmail.com> wrote:
>
>> Ummm..
>> Algorithm:
>> Start from the right of the array,
>> make the last element of B to 0,
>> initialize a variables counter to 0 and max to A[end];
>>
>> LOOP:
>> and now move from right to left,
>> if the next element of the left element > max
>> increment counter and assign it to that B[ n - element ] index.
>> max = that element.
>> if the next element is smaller, assign 0 and repeat LOOP
>> if the next element's index is 0, check and exit
>>
>> \/
>> A : ( 4, 3, 1, 2 )
>> B : ( 0, 0, 0, 0 )
>> counter = 0;
>> max = 2;
>>
>> \/
>> A : ( 4, 3, 1, 2 )
>> B : ( 0, 0, 0, 0 )
>> counter = 1;
>> max = 2;
>>
>> \/
>> A : ( 4, 3, 1, 2 )
>> B : ( 0, 0, 0, 0 )
>> counter = 2;
>> max = 2;
>> 3 > max i.e. 2
>> b[n - 3] = counter => b[1] = 2
>> max = 3;
>>
>> \/
>> A : ( 4, 3, 1, 2 )
>> B : ( 0, 0, 0, 0 )
>> counter = 3;
>> max = 3;
>> 4 > max i.e. 3
>> b[n - 4] = counter => b[0] = 3
>>
>> Edge Cases: It shall remain all 0's for all same numbers as well as
>> ascending numbers.
>>
>>
>>
>>
>> On Tue, Oct 4, 2011 at 7:13 AM, DIVIJ WADHAWAN <divij...@gmail.com>wrote:
>>
>>> int B[sizeof(A)];
>>> int k=0 , j ;
>>> for(j=i;j<n;j++)
>>> {
>>> if (A[j] < A[i])
>>> B[k++]=A[j];
>>>
>>> }
>>>
>>>
>>> On Tue, Oct 4, 2011 at 5:30 AM, Abraham <freedomsou...@gmail.com> wrote:
>>>
>>>> Hi Vikram!
>>>> Obviously The naivest solution is O(n2). Could you give a hint for
>>>> this problem?
>>>>
>>>>
>>>> On Oct 3, 4:39 pm, Vikram Singh <singhvikram...@gmail.com> wrote:
>>>> > Given an array say A=(4,3,1,2). An array B is formed out of this in
>>>> > such a way that B[i] = no. of elements in A, occuring on rhs of A[i],
>>>> > which are less then A[i].
>>>> > eg.for the A given, B is (3,2,0,0).
>>>> > Here A of length n only contains elements from 1 to n that too
>>>> > distinct..
>>>> > Now the problem is:
>>>> > 1). You are given with any such A. Find out corresponding B?
>>>> >
>>>> > 2). You are given with any such B. Find out corresponding A?
>>>> >
>>>> > Please provide solution in O(n),if possible??
>>>>
>>>> --
>>>> 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.
>>>
>>
>>
>>
>> --
>> Anup Ghatage
>>
>> --
>> 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.
