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
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.*
@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
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,
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
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
@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
@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
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
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
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
@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
@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
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
@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]
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)
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
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;
@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
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;
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
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,
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],
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
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 =
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,
@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
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
@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
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)
@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
@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
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
@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
@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
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,
@ 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,
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
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
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
@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
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
@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
@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
@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
@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 =
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 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
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
@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
@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,
@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
@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
@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
@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
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
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
@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
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
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
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
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
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]
@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
@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
65 matches
Mail list logo
