[algogeeks] Re: Array problem
Without the memory constraint, you just keep a minheap heap with the k largest elements. For every new number, if the heap is not full, add the number. Otherwise compare it to the smallest item in the heap, and if it is larger replace that item with the new one and downheap. The memory constraint makes no sense. For example, if K=1, you must remember the largest number you have seen using zero memory. If I give you one 32-bit number, and you later give it back to me, you must have used 32 bits of storage to keep that number. Or are you distinguishing between disk storage and memory? Don On Thursday, August 8, 2013 1:02:08 AM UTC-4, payel roy wrote: There is a stream of numbers coming in and you have to find K largest numbers out of the numbers received so far at any given time. Next problem is that a constraint is added. memory is limited to m. m k. How would you achieve the goal still. -- 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
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.
[algogeeks] Re: Array Problem
@arun..
Couple of questions need to be clarified :
1) Are all the numbers given in the unsorted array +ive integers.. ?
2) By 2 equal arrays do you mean that both the arrays should be of size N/2
(where N is even) .. ?
If the above assumptions are true then we can use the following recurrence
to solve the problem:
/* I have excluded the base condition initializations..*/
F(i, j, k) = ( (i j) ? F(i-1,j, k) : 0 ) || F( i-1, j-1, k - v[i] )
Only those values of F would be calculated for which the condition i=j
holds true..
Here,
v - unsorted array..
i - sub-array of first i elements of v
j - no. of elements picked out of the first i elements
k - the sum obtained by picking j elements out of the first i element
subarray..
Calculate all the values from F(0,0,0) -- F(N, N/2, S) ( for all F(i, j,
k) 's where i=j )
where S = (sum of the unsorted array) / 2 ...
F(i,j,k) will hold only one of the either 2 values :
0 - not possible to make a sum of K for (i, j) pick
1 - possible to make a sum of K for (i, j) pick..
Once all the values have been calculated we have to pick the max { R }
for which F(N, N/2, R) = 1, where 0 = R = S
Thereafter the min difference of 2 equal arrays would be:
(Sum of the unsorted array) - 2*R
On Wednesday, 7 November 2012 19:43:12 UTC+5:30, Arun wrote:
Given an unsorted array, how to divide them into two equal arrays whose
difference of sum is minimum.
--
[algogeeks] Re: Array Problem
I think that the problem specifies that the two arrays be of equal
size.
Don
On Nov 16, 9:12 am, bharat b bagana.bharatku...@gmail.com wrote:
@ vishal :let array be {5,2,1,1} == as per u'r algo ={1,2},{1,5} are sets
difference is 3 .. but the sol is {5}{1,1,2} == diff = 1;
On Fri, Nov 16, 2012 at 10:12 AM, vishal chaudhary vishal.cs.b...@gmail.com
wrote:
Hi
Sorry for that as i misinterpreted the question.
for the difference to be minimum, i think(not completely sure) we can
first sort the array
and then we can start putting the elements at even index in the last part
of the array and the odd ones in the starting in the new array
you can do this in the same array itself i guess but you have to do some
kind of shifting.
by doing this for all the elements and dividing them into two groups.
I hope this helps.
Vishal
On Fri, Nov 16, 2012 at 9:46 AM, bharat b
bagana.bharatku...@gmail.comwrote:
@ vishal : how can u divide an array into 2 groups whose difference is
maximum in O(1). why max?
solution :http://www.youtube.com/watch?v=GdnpQY2j064
On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary
vishal.cs.b...@gmail.com wrote:
Hi
you can first sort the array which can be done in O(nlogn) complexity if
the number of items in the array is n.
Then using the indexing of arrays you can divide the array into two
groups whose difference is going to be maximum and this can be done in
O(1)
complexity.
So the complete algorithm is going to take O(nlogn) complexity.
Kindly share an alternative algorithm if you find one with lower
complexity.
Vishal
On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra reserve4placem...@gmail.com
wrote:
Given an unsorted array, how to divide them into two equal arrays whose
difference of sum is minimum.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array problem
use the concept of segment tree+lazy propagation
On Saturday, August 25, 2012 2:39:54 AM UTC+5:30, wentworth miller wrote:
Hi,
You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th to y-th. It means
that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).
1=N=5 and
t is the number of test cases where 1=t=10
all numbers fit in the 32 bit integer range...
suggest some solution..
here is my solution
but it is giving wrong answer fo some unknown test case...plz suggest me
the test case where i am getting wrong answer
#includestdio.h
#includemath.h
int main()
{
int list[5],i,n,j,sum,k,l;char c;long t;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
for(i=0;in;i++)
{
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);
}
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);
t=2*t;
while(t)
{
sum=0;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);
fflush(stdin);
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d
%d,k,l);
if(c=='Q')
{
for(i=k-1;il-1;i++)
{
for(j=i+1;jl;j++)
{
if(list[i]==list[j])
break;
else if((j==l-1) (list[i]!=list[j]))
{
sum=sum+list[i];
}
}
}
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%d\n,sum+list[l-1]);
}
if(c=='U')
{
list[k-1]=l;
}
t--;
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/wLRpyiBiLuoJ.
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
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.
[algogeeks] Re: array problem
@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/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://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.
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.
[algogeeks] Re: Array Problem
@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.
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.
[algogeeks] Re: Array Problem
@Pranav: This could fail if N sqrt(maxint) and a sufficient number of A[i] have the same value so that A[A[i]] N*N, which overflows. Dave On Feb 15, 1:08 am, Pranav meetpranav...@gmail.com wrote: Array 'A' contains N elements st A[i] =k N Now, Iterate over the array. Let k=A[i] If A[i] N then k=A[i] mod N go to A[k] and write A[k] = A[k] + N So, lets take a sample array of size 5: 1,2,1,0,4 i=0: k=A[i]=1; A[i] 5; A[1] = A[1] + 5 = A[1] = 7 = A = 1,7,1,0,4 i=1: k=A[i]=7; A[i] 5; k=A[i] mod N = k=2 = A[2] = A[2] + 5 = A=1,7,6,0,4 i=2: k=A[i]=6; A[i] 5; k=A[i] mod N = k=1 = A[1] = A[1] + 5 = A=1,12,6,0,4 i=3: k=A[i]=0; A[i] 5; k=0 = A[0] = A[0] + 5 = A=6,12,6,0,4 i=4: k=A[i]=4; A[i] 5; k=4 = A[4] = A[4] + 5 = A=6,12,6,0,9 I'm using the fact that: (c*n + a) mod n =a Now, while searching, for say i=1, k=A[i] = k=12 count=int(k/5) Let me know if any test case fails. -- 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.
[algogeeks] Re: Array Problem
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.
[algogeeks] Re: Array Problem
Array 'A' contains N elements st A[i] =k N Now, Iterate over the array. Let k=A[i] If A[i] N then k=A[i] mod N go to A[k] and write A[k] = A[k] + N So, lets take a sample array of size 5: 1,2,1,0,4 i=0: k=A[i]=1; A[i] 5; A[1] = A[1] + 5 = A[1] = 7 = A = 1,7,1,0,4 i=1: k=A[i]=7; A[i] 5; k=A[i] mod N = k=2 = A[2] = A[2] + 5 = A=1,7,6,0,4 i=2: k=A[i]=6; A[i] 5; k=A[i] mod N = k=1 = A[1] = A[1] + 5 = A=1,12,6,0,4 i=3: k=A[i]=0; A[i] 5; k=0 = A[0] = A[0] + 5 = A=6,12,6,0,4 i=4: k=A[i]=4; A[i] 5; k=4 = A[4] = A[4] + 5 = A=6,12,6,0,9 I'm using the fact that: (c*n + a) mod n =a Now, while searching, for say i=1, k=A[i] = k=12 count=int(k/5) Let me know if any test case fails. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/wh65xNNjRksJ. 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.
[algogeeks] Re: Array Problem??
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.
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.
[algogeeks] Re: array problem
It would work i guess
On Aug 21, 1:49 pm, Sanjay Rajpal srn...@gmail.com wrote:
let n be the no.of integers in the array :
int i=1,a;
int zero,one;
for(int a=1;a=32;a++)
{
zero=0;
one=0;
for(int j=0;jn;j++)
{
if(a[j] i)
{
one++;
}
else
{
zero++;
}
}
if(one zero)
{
printf(1s are more \n);
}
else
{
printf(0s are more \n);
}
i=i1;
}
Correct me if m wrong.
Sanju
:)
On Sun, Aug 21, 2011 at 1:28 AM, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
yeah i took it in the another way..i ll post it v soon
On 8/21/11, himanshu kansal himanshukansal...@gmail.com wrote:
problem: There is an array containing integers.
for every bit in the integer,you have to print a 1 if no of 1s
corresponding to that bit is more than no of 0s corresponding to that
bit (counting that bit in all the integers) otherwise print a 0(if no
of 0s corresponding to that bit are more).
this you have to do for all bits in the integers.
assumption:integers are of 32bits.
no of integers in array are odd...(i.e. there is no case like no. of
1s=no. of 0s)
i have done this by counting the no of 1s and 0s for all bits.
but can anyone suggest any other efficient approach (somewhat using
bitwise operators).
--
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*
Comp Engg.
NIT Kurukshetra
+91 8950264227
--
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: Array problem
@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.
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.
[algogeeks] Re: array problem
@Jalaj: What is the work for each of the operations? I presume that get is O(1), but don't know if reverse is O(1) or O(end-start). Dave On Feb 10, 12:07 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: sort the input array. only following operations on array is allowed: 1)get(index) -gets the element at that index 2)reverse(int start,int end) - example reverse(1,3) for the array [1,2,3,4,5] will return [1,4,3,2,5] better then nlogn -- With Regards, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems Final Year Undergraduate, 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.
[algogeeks] Re: array problem
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.
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
[algogeeks] Re: Array Problem
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? -- 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: Array Problem
@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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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.
[algogeeks] Re: Array Problem
@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
.
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.
[algogeeks] Re: Array Problem
@Nikhil: A = {0,2,2}, B = {0,0,4}.
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).
Dave
On Aug 19, 2:24 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
@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.-Hidequoted 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,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd-
Hide quoted text -
-
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
[algogeeks] Re: Array Problem
@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
.
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.-Hidequoted 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,
[algogeeks] Re: Array Problem
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
.
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.-Hidequotedtext -
- 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
[algogeeks] Re: Array Problem
@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
.
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
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
[algogeeks] Re: Array Problem
@Chonku, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2).
Dave
On Aug 18, 7:52 am, Chonku cho...@gmail.com wrote:
1. Sum all the elements of both arrays. If the sum are same then perform
step 2. If the sum is not different, then arrays are different.
2. Xor elements of first array and then xor the result with elements of
second array. If result is zero, then the arrays are same.
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
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@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.comwrote:
@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
.
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
.
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.- 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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@Chonku, Make that: Your algorithm seems to fail on A = {0,1,-2), B =
(0,2,-3). I was thinking onwa-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:57 pm, Dave dave_and_da...@juno.com wrote:
@Chonku, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2).
Dave
On Aug 18, 7:52 am, Chonku cho...@gmail.com wrote:
1. Sum all the elements of both arrays. If the sum are same then perform
step 2. If the sum is not different, then arrays are different.
2. Xor elements of first array and then xor the result with elements of
second array. If result is zero, then the arrays are same.
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
.
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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@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.comwrote:
@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
.
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
.
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.-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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
It would be great if they have the likes and dislike like in yahoo answers so that correct or rather best solutions can be looked at immediately then subsequently the other solutions!! second, if u cud give the link to the problem, even we can try the problem and submit it and gain some confidence that we code rite :) Anyways here's the solution i propose 1) sort the array( keep track of their original indices!) from now on all operations on sorted array.. 2) since sorted, we need to locate i and j in sorted array such that index[j] - index[i] is maximum and i j (looks similar to problem ah! i am wondering too)(i j guarantees a[j] - a[i] 0 ) 3) min[i] store the smallest index till i - 1, maximize i - min[i] O(nlogn) that too due to sorting :( ;) hope i am right and clear :) -- 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 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.
[algogeeks] Re: Array Problem
Problme is not clear. Quesrtions: 1. Is the array all of positive numbers if yes then sort the array in ascending order. Now for every j, ji and i,j =n, A[j]A[i] and so A[j]-A[i] 0. Now if we want max(j-i) such that A[j]-A[i]0, it has to be j=n, the last element of A and i=1, the first element of A Time Complexity = O(nlogn) for sorting. 2. Is array consisting of +ve and -ve numbers? Again sort in ascending order(nlogn). We know A[j] is max of all elements. If A[j] = 0, then no solution exists. Else if A[j] +ve then again j=n, the last element of A and i=0 the first element is answer. Sourav Sain 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
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.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.
[algogeeks] Re: Array Problem
@sourav : if I understood problem correctly , you can't change the
list ( hence you can't sort ).
and list can containt + . - ive ints .
e.g. say list is
7 9 1 -4 8 0 0 0 3 1 0
Here answer is index(0) - index(-4) = 11
@divya : didn't get what you said , but guess you also thought of
sorting array .
Correct me if I am wrong here.
-Manish
On Jun 12, 2:48 pm, 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.
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.
