Re: [algogeeks] Re: Array Problem
I was going through this problem on stackoverflow, and I found this classic article on this very topic http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem Definitely, worth a read. -- * * *thanks regards,* *Avinesh Kumar National Institute of Technology, Calicut.* *Kerala- 673601* *+91 7849080702* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: array problem
interesting discussion going on the question, check this link-- http://stackoverflow.com/questions/9442958/find-the-element-occurring-b-times-in-an-an-array-of-size-nkb -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Fri, Feb 17, 2012 at 12:25 PM, atul anand atul.87fri...@gmail.comwrote: @Siddhartha : doing bitwise addtiton may result into overflow if values are large. correct me if i am wrong. On Fri, Feb 17, 2012 at 10:04 AM, Siddhartha Banerjee thefourrup...@gmail.com wrote: convert the numbers into base k... and do bitwise addition of numbers, where bit(a)+bit(b)=bit(a+b)mod(k) of you convert all the numbers into base k and add them bitwise in a variable say x, then the numbers occuring nk times vanish, and the final result stored in x is a+a++a(b times) where a is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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.
Re: [algogeeks] Re: array problem
@amol : actually complexity you have asked for is like saying finding solution in linear time. because we need to traverse whole array once atleast to find the solution and total size of array is n*k+b=N. so required complexity is O(N). so we can use hashmap to solve this problem. On Fri, Feb 17, 2012 at 4:19 AM, Dave dave_and_da...@juno.com wrote: @Amol: Since you don't restrict using extra space, use hashing or do a radix sort, either being O(n*k+b). Dave On Feb 15, 12:07 pm, Amol Sharma amolsharm...@gmail.com wrote: Given an array of size n*k+b.In this array n elements are repeated k times and 1 elements are repeated b times.find the Elements which is repeated b time.( O(n*k+b) expected ) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99 http://in.linkedin.com/pub/amol-sharma/21/79b/507 http://www.simplyamol.blogspot.com/ -- 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.
Re: [algogeeks] Re: array problem
any other solution other than hashingbcoz say numbers are very very largeyai want a linear solution i first choice was also hashing.but the interviewer wanted something other than that... -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Fri, Feb 17, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.com wrote: @amol : actually complexity you have asked for is like saying finding solution in linear time. because we need to traverse whole array once atleast to find the solution and total size of array is n*k+b=N. so required complexity is O(N). so we can use hashmap to solve this problem. On Fri, Feb 17, 2012 at 4:19 AM, Dave dave_and_da...@juno.com wrote: @Amol: Since you don't restrict using extra space, use hashing or do a radix sort, either being O(n*k+b). Dave On Feb 15, 12:07 pm, Amol Sharma amolsharm...@gmail.com wrote: Given an array of size n*k+b.In this array n elements are repeated k times and 1 elements are repeated b times.find the Elements which is repeated b time.( O(n*k+b) expected ) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99 http://in.linkedin.com/pub/amol-sharma/21/79b/507 http://www.simplyamol.blogspot.com/ -- 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.
Re: [algogeeks] Re: array problem
convert the numbers into base k... and do bitwise addition of numbers, where bit(a)+bit(b)=bit(a+b)mod(k) of you convert all the numbers into base k and add them bitwise in a variable say x, then the numbers occuring nk times vanish, and the final result stored in x is a+a++a(b times) where a is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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.
Re: [algogeeks] Re: array problem
can u explain with a explain what r u trying to say ? -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Fri, Feb 17, 2012 at 10:04 AM, Siddhartha Banerjee thefourrup...@gmail.com wrote: convert the numbers into base k... and do bitwise addition of numbers, where bit(a)+bit(b)=bit(a+b)mod(k) of you convert all the numbers into base k and add them bitwise in a variable say x, then the numbers occuring nk times vanish, and the final result stored in x is a+a++a(b times) where a is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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.
Re: [algogeeks] Re: array problem
@Siddhartha : doing bitwise addtiton may result into overflow if values are large. correct me if i am wrong. On Fri, Feb 17, 2012 at 10:04 AM, Siddhartha Banerjee thefourrup...@gmail.com wrote: convert the numbers into base k... and do bitwise addition of numbers, where bit(a)+bit(b)=bit(a+b)mod(k) of you convert all the numbers into base k and add them bitwise in a variable say x, then the numbers occuring nk times vanish, and the final result stored in x is a+a++a(b times) where a is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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.
Re: [algogeeks] Re: Array Problem
I think for count it should be count=(int)(k/N), instead of (int)k/5... On Wed, Feb 15, 2012 at 6:00 PM, TUSHAR tusharkanta.r...@gmail.com wrote: @amrit,@Pranav and others : Thanks a lot.. On Feb 15, 11:35 am, amrit harry dabbcomput...@gmail.com wrote: @tushar lower bound for sorting an array is nlogn. http://www.bowdoin.edu/~ltoma/teaching/cs231/fall11/Lectures/6-moreso... On Wed, Feb 15, 2012 at 11:16 AM, TUSHAR tusharkanta.r...@gmail.com wrote: That means,,,we have to sort the array first in O(n). Is there any way to sort the array inplace in O(n) ? -- 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. -- AMRIT -- 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. -- *Priyatosh Tiwari* *B. Tech. Third Year(CSE)* *MNNIT 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.
Re: [algogeeks] Re: Array Problem
heres a O(n) solution.. correct me if am wrong..
1. In order to get the count in O(1) we need to place the count of each
number in their respective index.So before storing the count we need to
swap the nos. in such a way that all k=n are at their respective
index.This can be done in O(n)
int arr[]={1,2,1,0,4};
int sz=sizeof(arr)/sizeof(int);
int x,y;
for(int i=0;isz;i++)
{
while(arr[i]!=arr[arr[i]])
{
x=arr[i];
y=arr[arr[i]];
arr[i]=y;
arr[x]=x;
}
}
This will take O(n) time ...as for every loop we are setting one number to
its respective index and then moving to the next number.
2. Now set the count to -1 for all i..such that arr[i] equal to i.
for(int i=0;isz;i++)
{
if(arr[i]==i)
arr[i]=-1;
}
3. Now for all the numbers that are 0 ,we need to increment the count in
their respective index.And set their count =0 as there is no such number
for which arr[i]==i.
for(int i=0;isz;i++)
{
if(arr[i]0)
{
arr[arr[i]]--;
arr[i]=0;
}
}
4.Now this array contains the count at their respective index.
int fun(int arr[],int x)
{
return -arr[x];
}
On Wed, Feb 15, 2012 at 10:48 PM, Dave dave_and_da...@juno.com wrote:
@Tushar: If we are going to use A[i] as an index into the array A[],
we must have 0 = A[i] N.
We can use a negative in A[i] to indicate that i occurs -A[i] times.
The code would look something like this:
//preprocessing...
int i, j, m;
for( i = 0 ; i N, ++i )
{
j = A[i];
while( j = 0 )
{
if( A[j] = 0 )
{
m = A[j];
A[j] = -1;
j = m;
if( j = i ) break;
}
else
{
A[j]--;
break;
}
}
}
Here is how this works: For each value of i, if A[i] 0, we already
have processed it, so nothing more is required. Otherwise, suppose
that A[i] has the value j. Then if A[j] 0 then we already have
processed at least one occurrence of j, so we just decrement A[j] to
indicate that an additional value j has occurred in A. But if A[j] =
0, this is the first time j has occurred. We set the value of A[j] to
-1 to indicate that j has occurred once, but before we lose the value
of A[j], we have to process its value. This results in the while loop
to run through the chain of numbers until we get to an entry we
already have processed.
Prerocessing is O(N) because the statement A[j] = -1 in the while loop
can be executed at most k times and A[j]-- can be executed at most N-1
times during all iterations of the for loop. And since one of these is
executed on every iteration of the while loop, the while loop itself
can be executed no more than N+k-1 2*N times during all iterations
of the for loop.
//determining count of number of original A[i] == x...
count = A[x] 0 ? -x : 0;
Dave
On Feb 14, 10:10 pm, TUSHAR tusharkanta.r...@gmail.com wrote:
Given an array of size N having numbers in the range 0 to k where
k=N, preprocess the array inplace and in linear time in such a way
that after preprocessing you should be able to return count of the
input element in O(1).
Please give some idea !!
Thanks..
--
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.
--
*Dheeraj Sharma*
--
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.
Re: [algogeeks] Re: Array Problem
@amit : it is valid for comparison based model.. On Wed, Feb 15, 2012 at 12:05 PM, amrit harry dabbcomput...@gmail.comwrote: @tushar lower bound for sorting an array is nlogn. http://www.bowdoin.edu/~ltoma/teaching/cs231/fall11/Lectures/6-moresorting/sortLB.pdf On Wed, Feb 15, 2012 at 11:16 AM, TUSHAR tusharkanta.r...@gmail.comwrote: That means,,,we have to sort the array first in O(n). Is there any way to sort the array inplace in O(n) ? -- 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. -- AMRIT -- 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.
Re: [algogeeks] Re: Array Problem??
B[n]=0;
for i=n to 1
{
if(A[i-1]=A[i])
B[i-1]=B[i];
else
B[i-1]=B[i]+1;
}
O(n) solution.
Correct me if I am wrong.
On Tue, Oct 4, 2011 at 2:07 PM, anshu mishra anshumishra6...@gmail.comwrote:
int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
int mid = (s+e)/2;
if (mid x) return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
else return count(x, tree, s, mid, 2*n+1);
}
main()
{
for(i=n-1;i=0; i--)
{
sol[i] = insert(ar[i], tree, 0, n-1, 0)
}
}
--
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.
Re: [algogeeks] Re: Array Problem??
for second part maintain an array of c[n-1] elements initialized to 1. for given count in B[i] from i=o,start counting 1's in c. at that (count)==b[i]+1,assume at c[j] set c[j]=0 and a[i]=j; its O(n2) :-( -- 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.
Re: [algogeeks] Re: Array Problem??
int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
int mid = (s+e)/2;
if (mid x) return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
else return count(x, tree, s, mid, 2*n+1);
}
main()
{
for(i=n-1;i=0; i--)
{
sol[i] = insert(ar[i], tree, 0, n-1, 0)
}
}
--
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.
Re: [algogeeks] Re: Array Problem??
int B[sizeof(A)];
int k=0 , j ;
for(j=i;jn;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.
Re: [algogeeks] Re: Array Problem??
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;jn;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.
Re: [algogeeks] Re: Array Problem??
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;jn;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.
Re: [algogeeks] Re: Array Problem??
@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.comwrote:
int B[sizeof(A)];
int k=0 , j ;
for(j=i;jn;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.
Re: [algogeeks] Re: Array Problem??
use segment tree or binary index tree to solve 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 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.
Re: [algogeeks] Re: Array Problem??
@anshu: pls elaborate... give an example... On Tue, Oct 4, 2011 at 9:51 AM, anshu mishra anshumishra6...@gmail.comwrote: use segment tree or binary index tree to solve 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 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.
Re: [algogeeks] Re: Array problem
@MONSIEUR.. someone once saidTHE SECRET OF SUCCESS IS TO NEVER REVEAL YOUR SOURCES... ;)...:P..:P On 5/22/11, MONSIEUR monsieur@gmail.com wrote: @piyush: excellent buddybtw what was the initial spark...???.:-) On May 21, 1:01 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote: @Amit JaspalThe algo given by me works for the given case..check it On 5/20/11, Anurag Bhatia abhati...@gmail.com wrote: Just need some clarification; sorry I joined the thread late. What are we trying maximize? A[j] -A[i] such that ij? or j-i such that A[i]A[j]? --Anurag On Fri, May 20, 2011 at 12:34 AM, Kunal Patil kp101...@gmail.com wrote: @ Piyush: Excellent Solution...It appears both Correct and O(n)...Good work !![?] Just a minor correction in your algo.[?] while(B[i]C[j]) j++; must also check for J's bound as: while ( j ( sizeof(A)/sizeof(A[0]) ) B[i]C[j] ) j++; Or it will crash when J goes out of bound and we try to reference C[j]. Nywayz..thnx for the solution and algo !! -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* 363.gif 1KViewDownload 360.gif 1KViewDownload -- 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. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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.
Re: [algogeeks] Re: array problem
This problem is close than this: http://uva.onlinejudge.org/external/103/10327.html I found this: http://en.wikipedia.org/wiki/Pancake_sorting Wladimir Araujo Tavares *Federal University of Ceará * On Fri, Feb 11, 2011 at 10:57 AM, juver++ avpostni...@gmail.com wrote: @jalaj please ignore my prevoius post, misread the problem. -- 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.
Re: [algogeeks] Re: array problem
@jalaj please ignore my prevoius post, misread the problem. -- 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.
Re: [algogeeks] Re: array problem
@ dave assume reverse also O(1) @juver will you elaborate a bit dude On Thu, Feb 10, 2011 at 8:21 PM, juver++ avpostni...@gmail.com wrote: Cartesian tree will do. -- 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. -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems B.Tech 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.
Re: [algogeeks] Re: Array Problem
can you please explain more in detail the logic for XORing the index.
On 22.08.2010 07:53, UMarius wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwalnikhil.bhoja...@gmail.com wrote:
@marius Why are you xorring the indexes along with nos.?any special reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMariusmar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the code:
for(int i = 0 ; i arr1.Length ; i++)
{
arr1XOR ^= arr1[i];
arr1XOR ^= i;
arr1SUM += arr1[i];
arr1MUL *= arr1[i];
}
for (int i = 0; i arr2.Length; i++)
{
arr2XOR ^= arr2[i];
arr2XOR ^= i;
arr2SUM += arr2[i];
arr2MUL *= arr2[i];
}
if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL ==
arr2MUL)
{
//SAME VALUES - IDENTICAL ARRAYS
}
else
{
//NOT IDENTICAL
}
Please correct me if I'm wrong.
Marius.
On Aug 22, 3:45 am, Davedave_and_da...@juno.com wrote:
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same values,
possibly in a different order.
Dave
On Aug 21, 11:01 am, UMariusmar...@aseara.ro wrote:
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :) ...
Given two arrays of numbers, find if each of the two arrays have the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups
.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology,
Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd
--
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: Array Problem
a={1,2,2,3,4}
b={1,2,3,3,4}
in this case???
elements are not equal but they certainly consist equal set of
integers(1,2,3,4) which is what question says.
On Sun, Aug 22, 2010 at 7:53 AM, UMarius mar...@aseara.ro wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
@marius Why are you xorring the indexes along with nos.?any special
reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the code:
for(int i = 0 ; i arr1.Length ; i++)
{
arr1XOR ^= arr1[i];
arr1XOR ^= i;
arr1SUM += arr1[i];
arr1MUL *= arr1[i];
}
for (int i = 0; i arr2.Length; i++)
{
arr2XOR ^= arr2[i];
arr2XOR ^= i;
arr2SUM += arr2[i];
arr2MUL *= arr2[i];
}
if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL ==
arr2MUL)
{
//SAME VALUES - IDENTICAL ARRAYS
}
else
{
//NOT IDENTICAL
}
Please correct me if I'm wrong.
Marius.
On Aug 22, 3:45 am, Dave dave_and_da...@juno.com wrote:
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same
values,
possibly in a different order.
Dave
On Aug 21, 11:01 am, UMarius mar...@aseara.ro wrote:
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :)
...
Given two arrays of numbers, find if each of the two arrays have
the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology,
Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://
beta.freshersworld.com/communities/nitd
--
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.comalgogeeks%2bunsubscr...@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: Array Problem
Its easier to look at a property of numbers. It will be interesting to
evaluate/prove if two different arrays have same value for sum of elements
and sum of squares of the elements.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide counter eg.(if any)
step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes
proceed to step 2 else print fail
step2: if(sum of the elements and product of the non zero elements are
same in both arrays ) print arrays are same else print fail.
On Fri, Aug 20, 2010 at 4:26 AM, Dave dave_and_da...@juno.com wrote:
@Saikat: Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
B_1,
A_2 = B_2, etc. (where I have assumed that each array is sorted).
Usually, it takes 2N equations to determine 2N unknowns, although
other information about the solutions can lessen that number in
certain circumstances.
At least if you are going to propose something, do so only after you
have tested it on all of the combinations of up to four numbers
between -5 and 5.
Dave
On Aug 19, 11:52 am, Saikat Debnath saikat@gmail.com wrote:
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote:
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
Dave
On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
@Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
S1=0;S2=0;
M1=-1 and M2 =-4 (excluding 0 multiplication which i had
corrected)
M1!=M2 there fore it is correct.
Code:
bool check_arrays(vectorint v1,vectorint v2){
if(v1.size()!=v2.size())
return 0;
if(v1.size()==0v2.size()==0)
return 1;
int sum,product1,product2;
sum=0;product1=1;product2=1;
for(int i=0;iv1.size();i++){
sum+=v1[i];
sum-=v2[i];
if(v1[i]!=0)
product1*=v1[i];
if(v2[i]!=0)
product2*=v2[i];
}
if(sum==0(product1==product2))
return 1;
return 0;
}
On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com
wrote:
@Srinivas, Make that: Your algorithm seems to fail on A =
{0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of
twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com
wrote:
add one more thing to the solution suggested by nikhil
i.e;count the
number
of elements in array 1 and number of elements in array2 if
these two
values
are equal then after follow the algo proposed by nikhil
agarwal..
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Nikhil: Your algo seems to fail with following input.
What do you
say?
Arr1[]= {1,2,3}
Arr2[]={6}
On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
Sum all the elements of both the arrays..let it be s1 and
s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;
O(n)
On Tue, Aug 17, 2010 at 11:33 PM, amit
amitjaspal...@gmail.com
wrote:
Given two arrays of numbers, find if each of the two
arrays have
the
same set of integers ? Suggest an algo which can run
faster than
NlogN
without extra space?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%2bunsubscr...@googlegroups.com
Re: [algogeeks] Re: Array Problem
@Nikhil Agarwal: You cannot take extra memory and neither the range of
numbers is specified.
Counting will not be a viable option.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide counter eg.(if any)
step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes
proceed to step 2 else print fail
step2: if(sum of the elements and product of the non zero elements are
same in both arrays ) print arrays are same else print fail.
On Fri, Aug 20, 2010 at 4:26 AM, Dave dave_and_da...@juno.com wrote:
@Saikat: Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
B_1,
A_2 = B_2, etc. (where I have assumed that each array is sorted).
Usually, it takes 2N equations to determine 2N unknowns, although
other information about the solutions can lessen that number in
certain circumstances.
At least if you are going to propose something, do so only after you
have tested it on all of the combinations of up to four numbers
between -5 and 5.
Dave
On Aug 19, 11:52 am, Saikat Debnath saikat@gmail.com wrote:
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote:
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
Dave
On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
@Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
S1=0;S2=0;
M1=-1 and M2 =-4 (excluding 0 multiplication which i had
corrected)
M1!=M2 there fore it is correct.
Code:
bool check_arrays(vectorint v1,vectorint v2){
if(v1.size()!=v2.size())
return 0;
if(v1.size()==0v2.size()==0)
return 1;
int sum,product1,product2;
sum=0;product1=1;product2=1;
for(int i=0;iv1.size();i++){
sum+=v1[i];
sum-=v2[i];
if(v1[i]!=0)
product1*=v1[i];
if(v2[i]!=0)
product2*=v2[i];
}
if(sum==0(product1==product2))
return 1;
return 0;
}
On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com
wrote:
@Srinivas, Make that: Your algorithm seems to fail on A =
{0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of
twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com
wrote:
add one more thing to the solution suggested by nikhil
i.e;count the
number
of elements in array 1 and number of elements in array2 if
these two
values
are equal then after follow the algo proposed by nikhil
agarwal..
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Nikhil: Your algo seems to fail with following input.
What do you
say?
Arr1[]= {1,2,3}
Arr2[]={6}
On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
Sum all the elements of both the arrays..let it be s1 and
s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;
O(n)
On Tue, Aug 17, 2010 at 11:33 PM, amit
amitjaspal...@gmail.com
wrote:
Given two arrays of numbers, find if each of the two
arrays have
the
same set of integers ? Suggest an algo which can run
faster than
NlogN
without extra space?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group
Re: [algogeeks] Re: Array Problem
@marius Why are you xorring the indexes along with nos.?any special reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the code:
for(int i = 0 ; i arr1.Length ; i++)
{
arr1XOR ^= arr1[i];
arr1XOR ^= i;
arr1SUM += arr1[i];
arr1MUL *= arr1[i];
}
for (int i = 0; i arr2.Length; i++)
{
arr2XOR ^= arr2[i];
arr2XOR ^= i;
arr2SUM += arr2[i];
arr2MUL *= arr2[i];
}
if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL ==
arr2MUL)
{
//SAME VALUES - IDENTICAL ARRAYS
}
else
{
//NOT IDENTICAL
}
Please correct me if I'm wrong.
Marius.
On Aug 22, 3:45 am, Dave dave_and_da...@juno.com wrote:
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same values,
possibly in a different order.
Dave
On Aug 21, 11:01 am, UMarius mar...@aseara.ro wrote:
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :) ...
Given two arrays of numbers, find if each of the two arrays have the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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: Array Problem
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
@Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
S1=0;S2=0;
M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected)
M1!=M2 there fore it is correct.
Code:
bool check_arrays(vectorint v1,vectorint v2){
if(v1.size()!=v2.size())
return 0;
if(v1.size()==0v2.size()==0)
return 1;
int sum,product1,product2;
sum=0;product1=1;product2=1;
for(int i=0;iv1.size();i++){
sum+=v1[i];
sum-=v2[i];
if(v1[i]!=0)
product1*=v1[i];
if(v2[i]!=0)
product2*=v2[i];
}
if(sum==0(product1==product2))
return 1;
return 0;
}
On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote:
@Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote:
add one more thing to the solution suggested by nikhil i.e;count the
number
of elements in array 1 and number of elements in array2 if these two
values
are equal then after follow the algo proposed by nikhil agarwal..
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com
wrote:
@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com
wrote:
@Nikhil: Your algo seems to fail with following input. What do you
say?
Arr1[]= {1,2,3}
Arr2[]={6}
On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
Sum all the elements of both the arrays..let it be s1 and s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;
O(n)
On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com
wrote:
Given two arrays of numbers, find if each of the two arrays have
the
same set of integers ? Suggest an algo which can run faster than
NlogN
without extra space?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
- Show quoted text -- 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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
Re: [algogeeks] Re: Array Problem
@saikat ur algo fails with the test case a1=-2,-2 and a2=2,2
On Thu, Aug 19, 2010 at 10:22 PM, Saikat Debnath saikat@gmail.comwrote:
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote:
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
Dave
On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
@Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
S1=0;S2=0;
M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected)
M1!=M2 there fore it is correct.
Code:
bool check_arrays(vectorint v1,vectorint v2){
if(v1.size()!=v2.size())
return 0;
if(v1.size()==0v2.size()==0)
return 1;
int sum,product1,product2;
sum=0;product1=1;product2=1;
for(int i=0;iv1.size();i++){
sum+=v1[i];
sum-=v2[i];
if(v1[i]!=0)
product1*=v1[i];
if(v2[i]!=0)
product2*=v2[i];
}
if(sum==0(product1==product2))
return 1;
return 0;
}
On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com
wrote:
@Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2),
B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com
wrote:
add one more thing to the solution suggested by nikhil i.e;count
the
number
of elements in array 1 and number of elements in array2 if these
two
values
are equal then after follow the algo proposed by nikhil
agarwal..
On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}
On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan
raiskhan.i...@gmail.com
wrote:
@Nikhil: Your algo seems to fail with following input. What
do you
say?
Arr1[]= {1,2,3}
Arr2[]={6}
On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.com wrote:
Sum all the elements of both the arrays..let it be s1 and s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;
O(n)
On Tue, Aug 17, 2010 at 11:33 PM, amit
amitjaspal...@gmail.com
wrote:
Given two arrays of numbers, find if each of the two arrays
have
the
same set of integers ? Suggest an algo which can run faster
than
NlogN
without extra space?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
algogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups .com
Re: [algogeeks] Re: Array Problem
i meant make an array of indexes.. index[]={0,1...,n-1}
now sort the original array and move the elements of index array
accordingly..
now follow modelling expert's algo nd while taking largest-smallest check if
the index of largest in index array index of smallest in index array.
On 13 June 2010 08:38, Rohit Saraf rohit.kumar.sa...@gmail.com wrote:
@Satya: I don't think what you have coded will work.. though i have not
read the whole code.
Don't you think a simple divide and conquer scheme would work...(almost
like the mergesort)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
On Sat, Jun 12, 2010 at 9:06 PM, Satya satya...@gmail.com wrote:
This problem seems to be finding the maxdiff in an array.
int maxdiff ( int A[], int n ) {
// write your code here
int max_diff = A[1] - A[0];
int min_element = A[0];
int i;
for(i = 1; i n; i++)
{
if(A[i] - min_element max_diff)
max_diff = A[i] - min_element;
if(A[i] min_element)
min_element = A[i];
}
if(max_diff 0)
max_diff = 0;
return max_diff;
}
.
Satya
On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote:
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote:
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till you reach start
}
now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.
Average time o(n^2)
Worst case : let's say we have descending array of ints, theno(n^2)
Please suggest improvements
On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote:
given an array A of n elements.
for indexes j , i such that ji
maximize( j - i )
such that A[j] - A [ i ] 0 .
Any Algorithm less than O(n^2) would do.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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: Array Problem
@BALARUKESH i think the problem is to maximize the diffrence j-i according to condition and in your solution j can be less than i. This problem can be solved by sorting the array first, then taking diffrence. this solution is done in 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: Array Problem
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.com wrote:
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till you reach start
}
now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.
Average time o(n^2)
Worst case : let's say we have descending array of ints, theno(n^2)
Please suggest improvements
On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote:
given an array A of n elements.
for indexes j , i such that ji
maximize( j - i )
such that A[j] - A [ i ] 0 .
Any Algorithm less than O(n^2) would do.
--
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.comalgogeeks%2bunsubscr...@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: Array Problem
yes we need to maintain an array that shows the real indexes before sorting
and then loop on the elements and find the minimum index that appeared
before a number in the sorted array and subtract it from it's index
and find the maximum difference
On 6/12/10, divya jain sweetdivya@gmail.com wrote:
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.com wrote:
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till you reach start
}
now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.
Average time o(n^2)
Worst case : let's say we have descending array of ints, theno(n^2)
Please suggest improvements
On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote:
given an array A of n elements.
for indexes j , i such that ji
maximize( j - i )
such that A[j] - A [ i ] 0 .
Any Algorithm less than O(n^2) would do.
--
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.comalgogeeks%2bunsubscr...@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: Array Problem
This problem seems to be finding the maxdiff in an array.
int maxdiff ( int A[], int n ) {
// write your code here
int max_diff = A[1] - A[0];
int min_element = A[0];
int i;
for(i = 1; i n; i++)
{
if(A[i] - min_element max_diff)
max_diff = A[i] - min_element;
if(A[i] min_element)
min_element = A[i];
}
if(max_diff 0)
max_diff = 0;
return max_diff;
}
.
Satya
On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote:
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote:
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till you reach start
}
now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.
Average time o(n^2)
Worst case : let's say we have descending array of ints, theno(n^2)
Please suggest improvements
On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote:
given an array A of n elements.
for indexes j , i such that ji
maximize( j - i )
such that A[j] - A [ i ] 0 .
Any Algorithm less than O(n^2) would do.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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: Array Problem
@Satya: I don't think what you have coded will work.. though i have not read
the whole code.
Don't you think a simple divide and conquer scheme would work...(almost like
the mergesort)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sat, Jun 12, 2010 at 9:06 PM, Satya satya...@gmail.com wrote:
This problem seems to be finding the maxdiff in an array.
int maxdiff ( int A[], int n ) {
// write your code here
int max_diff = A[1] - A[0];
int min_element = A[0];
int i;
for(i = 1; i n; i++)
{
if(A[i] - min_element max_diff)
max_diff = A[i] - min_element;
if(A[i] min_element)
min_element = A[i];
}
if(max_diff 0)
max_diff = 0;
return max_diff;
}
.
Satya
On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote:
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote:
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till you reach start
}
now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.
Average time o(n^2)
Worst case : let's say we have descending array of ints, theno(n^2)
Please suggest improvements
On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote:
given an array A of n elements.
for indexes j , i such that ji
maximize( j - i )
such that A[j] - A [ i ] 0 .
Any Algorithm less than O(n^2) would do.
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
