Re: [algogeeks] Re: arrays
you can also go through the array printing the indexes, but what if I want to know the indexes of some certain elements? 2010/12/30 siva viknesh : > if we sort the first array along with the indexes ...in the next pass > we can directly print the indexes as result no > why should we do binary search in the next pass considering that > 2nd array is also sorted??? > > On Dec 29, 11:38 am, Abioy Sun wrote: >> Hello, >> >> 2010/12/29 Anand : >> >> > if I already have a structure indicating the position of the element in the >> > array. Then why do we need to sort. Question is to provide index of element >> > in O(nlogn). >> >> You do not have a structure before preprocessing the data, whose >> complexity is O(nlogn) via qsort. Once you zip the zip the two array, >> and sort the new array as @Wladimir and @juver++ mention, you can >> provide each certain element's index in O(logn) via bsearch. > > -- > 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.
[algogeeks] Re: arrays
You mentioned EXPECTED time, not the worst case. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
for each element i in A[n] do map (A[n],i) for each element j in B[n] do index = B[n] X[index] = map.get(index); This will traverse both the array once, so O(n+n) = O(n) time. On Dec 31, 1:44 pm, juver++ wrote: > of course, we should keep pair - element and its initial position -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
of course, we should keep pair - element and its initial position -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
@Wladimir For creating binary search for the first array, we need to arrange it in sorting order right? if we do so we will lose the index information unless we store it in a structure of arrays. On Thu, Dec 30, 2010 at 1:32 AM, Wladimir Tavares wrote: > My two cents: > > You use bsearch in the first array for each element of second array!! > > > Wladimir Araujo Tavares > *Federal University of Ceará > > * > > > > > > On Wed, Dec 29, 2010 at 3:05 PM, siva viknesh wrote: > >> if we sort the first array along with the indexes ...in the next pass >> we can directly print the indexes as result no >> why should we do binary search in the next pass considering that >> 2nd array is also sorted??? >> >> On Dec 29, 11:38 am, Abioy Sun wrote: >> > Hello, >> > >> > 2010/12/29 Anand : >> > >> > > if I already have a structure indicating the position of the element >> in the >> > > array. Then why do we need to sort. Question is to provide index of >> element >> > > in O(nlogn). >> > >> > You do not have a structure before preprocessing the data, whose >> > complexity is O(nlogn) via qsort. Once you zip the zip the two array, >> > and sort the new array as @Wladimir and @juver++ mention, you can >> > provide each certain element's index in O(logn) via bsearch. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: arrays
My two cents: You use bsearch in the first array for each element of second array!! Wladimir Araujo Tavares *Federal University of Ceará * On Wed, Dec 29, 2010 at 3:05 PM, siva viknesh wrote: > if we sort the first array along with the indexes ...in the next pass > we can directly print the indexes as result no > why should we do binary search in the next pass considering that > 2nd array is also sorted??? > > On Dec 29, 11:38 am, Abioy Sun wrote: > > Hello, > > > > 2010/12/29 Anand : > > > > > if I already have a structure indicating the position of the element in > the > > > array. Then why do we need to sort. Question is to provide index of > element > > > in O(nlogn). > > > > You do not have a structure before preprocessing the data, whose > > complexity is O(nlogn) via qsort. Once you zip the zip the two array, > > and sort the new array as @Wladimir and @juver++ mention, you can > > provide each certain element's index in O(logn) via bsearch. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: arrays
if we sort the first array along with the indexes ...in the next pass we can directly print the indexes as result no why should we do binary search in the next pass considering that 2nd array is also sorted??? On Dec 29, 11:38 am, Abioy Sun wrote: > Hello, > > 2010/12/29 Anand : > > > if I already have a structure indicating the position of the element in the > > array. Then why do we need to sort. Question is to provide index of element > > in O(nlogn). > > You do not have a structure before preprocessing the data, whose > complexity is O(nlogn) via qsort. Once you zip the zip the two array, > and sort the new array as @Wladimir and @juver++ mention, you can > provide each certain element's index in O(logn) via bsearch. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
Hello, 2010/12/29 Anand : > if I already have a structure indicating the position of the element in the > array. Then why do we need to sort. Question is to provide index of element > in O(nlogn). You do not have a structure before preprocessing the data, whose complexity is O(nlogn) via qsort. Once you zip the zip the two array, and sort the new array as @Wladimir and @juver++ mention, you can provide each certain element's index in O(logn) via bsearch. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
for each element in the second array apply binary search in first array. ie, For X[1] find 1 in first array with binary search. Time Complexity=O(nlogn) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
if I already have a structure indicating the position of the element in the
array. Then why do we need to sort. Question is to provide index of element
in O(nlogn).
On Tue, Dec 28, 2010 at 2:20 PM, Wladimir Tavares wrote:
> Hi Anad,
>
> You can create a struct with this information
>
> typedef struct TArray{
> int value;
> int index;
> };
>
> TArray a[100];
>
>
>
> Wladimir Araujo Tavares
> http://www.si.ufc.br/~wladimir
Re: [algogeeks] Re: arrays
Hi Anad,
You can create a struct with this information
typedef struct TArray{
int value;
int index;
};
TArray a[100];
Wladimir Araujo Tavares
http://www.si.ufc.br/~wladimir
Re: [algogeeks] Re: arrays
Now the question boils down to how to sorted the array preserving its index. On Tue, Dec 28, 2010 at 12:27 AM, juver++ wrote: > Sort first array preserving the initial position of the elements. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: arrays
@ Wladimir How do you get (1,3) (2,1) (3,6) (4,5) (5,2) (6,3) B'cos once you sort the array you lose its original index. On Tue, Dec 28, 2010 at 5:50 AM, Wladimir Tavares wrote: > Consider your example: > > > One is > > 2 5 1 6 4 3 > > other is > > 1 2 3 4 5 6. > > > After sorted the first array and keep the position you will have: > > > (1,3) > (2,1) > (3,6) > (4,5) > (5,2) > (6,3) > > O(n log n) > > for each value of the second array do a binary search in the first array > and discover the position > > O (log n) > > O (nlgn + lgn) > > > > On Tue, Dec 28, 2010 at 8:48 AM, Bhoopendra Singh > wrote: > >> Is second array sorted? >> >> >> On Tue, Dec 28, 2010 at 1:57 PM, juver++ wrote: >> >>> Sort first array preserving the initial position of the elements. >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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: arrays
Consider your example: One is 2 5 1 6 4 3 other is 1 2 3 4 5 6. After sorted the first array and keep the position you will have: (1,3) (2,1) (3,6) (4,5) (5,2) (6,3) O(n log n) for each value of the second array do a binary search in the first array and discover the position O (log n) O (nlgn + lgn) On Tue, Dec 28, 2010 at 8:48 AM, Bhoopendra Singh wrote: > Is second array sorted? > > > On Tue, Dec 28, 2010 at 1:57 PM, juver++ wrote: > >> Sort first array preserving the initial position of the elements. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: arrays
Is second array sorted? On Tue, Dec 28, 2010 at 1:57 PM, juver++ wrote: > Sort first array preserving the initial position of the elements. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@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 algoge...@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: arrays
Sort first array preserving the initial position of the elements. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
this can be done in O(n) using a stack . -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: arrays
for getting O(n), Counting sort will work but limitation is that you must
know max element possible in the array.
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Oct 8, 2010 at 5:41 AM, Anand wrote:
> Is there O(n) solution available for it?
>
>
> On Tue, Sep 28, 2010 at 7:19 AM, Nishant Agarwal <
> nishant.agarwa...@gmail.com> wrote:
>
>> #include
>> #include
>> int main()
>> {
>> int a[20],i,n,max,t,j,k;
>> printf("Enter the no. of elements\n");
>> scanf("%d",&n);
>> for(i=0;i> scanf("%d",&a[i]);
>> for(i=0;i> {
>> j=n-1;
>> max=0;
>> k=i;
>> while(i> {
>> if(a[j]=max)
>> {
>> max=a[j];
>> k=j;
>> j--;
>> }
>> else
>> j--;
>> }
>> t=a[i];
>> a[i]=a[k];
>> a[k]=t;
>> }
>> for(i=0;i> printf("%d\t",a[i]);
>> return 0;
>>
>> }
>>
>> On Tue, Sep 28, 2010 at 3:43 AM, Chi wrote:
>>
>>> Move-To-The-Front.
>>>
>>> On Sep 27, 11:58 pm, Anand wrote:
>>> > Given an array of integers, for each index i, you have to swap the
>>> value at
>>> > i with the first value smaller than A[ i ] that comes after index i
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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: arrays
Is there O(n) solution available for it?
On Tue, Sep 28, 2010 at 7:19 AM, Nishant Agarwal <
nishant.agarwa...@gmail.com> wrote:
> #include
> #include
> int main()
> {
> int a[20],i,n,max,t,j,k;
> printf("Enter the no. of elements\n");
> scanf("%d",&n);
> for(i=0;i scanf("%d",&a[i]);
> for(i=0;i {
> j=n-1;
> max=0;
> k=i;
> while(i {
> if(a[j]=max)
> {
> max=a[j];
> k=j;
> j--;
> }
> else
> j--;
> }
> t=a[i];
> a[i]=a[k];
> a[k]=t;
> }
> for(i=0;i printf("%d\t",a[i]);
> return 0;
>
> }
>
> On Tue, Sep 28, 2010 at 3:43 AM, Chi wrote:
>
>> Move-To-The-Front.
>>
>> On Sep 27, 11:58 pm, Anand wrote:
>> > Given an array of integers, for each index i, you have to swap the
>> value at
>> > i with the first value smaller than A[ i ] that comes after index i
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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: arrays
#include
#include
int main()
{
int a[20],i,n,max,t,j,k;
printf("Enter the no. of elements\n");
scanf("%d",&n);
for(i=0;i=max)
{
max=a[j];
k=j;
j--;
}
else
j--;
}
t=a[i];
a[i]=a[k];
a[k]=t;
}
for(i=0;i wrote:
> Move-To-The-Front.
>
> On Sep 27, 11:58 pm, Anand wrote:
> > Given an array of integers, for each index i, you have to swap the value
> at
> > i with the first value smaller than A[ i ] that comes after index i
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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 algoge...@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: arrays
Move-To-The-Front. On Sep 27, 11:58 pm, Anand wrote: > Given an array of integers, for each index i, you have to swap the value at > i with the first value smaller than A[ i ] that comes after index i -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Arrays
XOR all the elements from both arrays, the value that is left is x. On Sep 20, 5:06 pm, Anand wrote: > Two unsorted arrays are given A[n] and B[n+1]. Array A contains n integers > and B contains n+1 integers of which n are same as in array B but in > different order and one extra element x. Write an optimized algorithm to > find the value of element x. Use only one pass of both arrays A and B. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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: Arrays
no need to addi all element if overflow is feared , subtract values
for given index in the loop
something like this
result = 0 ;
for(count = 0; count < n ;count ++){
result += (B[count]-A[count]);
}
result += B[count] ; //! this is the answer...
-Manish
On Sep 21, 9:44 am, Baljeet Kumar wrote:
> There can be overflow in case of adding up all the elements. Use Xor
> instead.
>
>
>
>
>
> > int result = 0;
> > for (int i = 0; i < n ;i++){
> > result ^= A[i]^B[i];
> > }
>
> > result ^= B[n]; <=== (correction)
> > result is the number we need.
>
> > On Tue, Sep 21, 2010 at 9:48 AM, vishal raja wrote:
>
> >> add up all the elements in array A say sumA and array B say sumB
> >> ,substract the sumA from sumB... You'll get the element.
>
> >> On Tue, Sep 21, 2010 at 5:36 AM, Anand wrote:
>
> >>> Two unsorted arrays are given A[n] and B[n+1]. Array A contains n
> >>> integers and B contains n+1 integers of which n are same as in array B but
> >>> in different order and one extra element x. Write an optimized algorithm
> >>> to
> >>> find the value of element x. Use only one pass of both arrays A and B.
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algoge...@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 algoge...@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.
>
> > --
> > Baljeet Kumar
>
> --
> Baljeet Kumar
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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: arrays
You can count such pairs using the merge sort algorithm.
While in merge sort if at any place you need swapping then increase
the count.
here is the code
long long merge(long long *a,long long l,long long m,long long r)
{
long long i=l,j,k,t,c=0;
long long ml[MAX_SIZE];
long long n1=m-l+1;
j=l,k=m+1;
while(j<=m&&k<=r)
{
if(a[j]<=a[k])
ml[l]=a[j],l++,j++;
else{
ml[l]=a[k],k++;
c+=n1-j+i;
l++;
}
}
if(j>m)
for(t=k;t<=r;t++)
ml[t]=a[t];
else
for(t=j;t<=m;t++)
ml[l+t-j]=a[t];
for(j=i;j<=r;j++)
a[j]=ml[j];
return c;
}
long long mergesort(long long *a,long long l,long long r)
{
if(l>=r)
return 0;
long long m=(l+r)/2;
return mergesort(a,l,m) + mergesort(a,m+1,r) + merge(a,l,m,r);
}
On Jun 27, 11:32 am, Amit Jaspal wrote:
> This is the famous Inversion Problem
> Hint: you can do it in O(nlogn) using a tweek in merge sort
>
> On Sun, Jun 27, 2010 at 11:26 AM, Anil C R wrote:
>
> > this is just brute force:
>
> > count = 0
> > for i in range(0, len(A)):
> > for j in range(i+1, len(A)):
> > if A[i] > A[j]:
> > count += 1
>
> > Time complexity = O(n**2)
> > Anil
>
> > On Sun, Jun 27, 2010 at 9:59 AM, sharad kumar
> > wrote:
>
> >> Give an unsorted array find count of pairs of numbers[a,b] where a > b
> >> and b comes after a in the array.
>
> >> Eg. {8,3,6,10,5}
>
> >> the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algoge...@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 algoge...@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 algoge...@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.
