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.*
Hi,
we can calculate the frequency of all element, Assign sort them in
increasing order of frequency.
then the first element of sorted list will be the return element.
0bn
we can implement it by Min Heap(which is based upon the frequency and
reorganise itself
as the frequency of element change
@Pankaj: Can you give more details of your algorithm, including the big-O
order of time and space. It certainly is not difficult to do it in O(n log
n) time and O(n) space, as this can be accomplished by a merge-sort. For
fixed data size, O(n) time and O(n) space can be achieved by a radix
if one can explin me this i think this problem will get solved
thanks
--mac
On Wed, May 8, 2013 at 12:02 AM, MAC macatad...@gmail.com wrote:
I was asked this in recent amazon onsite interview and asked o write code
Given an Array of integers . N elements occur k times and one element
sry link was not pasted
http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim
thanks
--mac
On Thu, May 9, 2013 at 12:40 AM, MAC macatad...@gmail.com wrote:
if one can explin me this i think this problem will get solved
@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
I don't think it can be done in better than O(n) space and time.
On Tue, Nov 22, 2011 at 9:28 PM, himanshu kansal
himanshukansal...@gmail.com wrote:
@SAM: in your first step, where you are xoring the unique elements, you
must be using some DS such as hashtable or something.
so space
@SAM: in your first step, where you are xoring the unique elements, you
must be using some DS such as hashtable or something.
so space complexity will be O(n).
can someone reduces this O(n) space complexity.because it wont be a
good approach if there are many elements in the
@SAMM: It sounds like a circular argument. How do you XOR all of the
unique elements without first finding the repeated ones?
Dave
On Nov 17, 11:24 am, SAMM somnath.nit...@gmail.com wrote:
Yes we can do so in O(n) .
First find the XOR of all unique elements using hash table or some other DS.
On 11/18/11, SAMM somnath.nit...@gmail.com wrote:
For example the array has ..
1 4 2 6 7 4 8 3..
xor the elements in the array will give (1^2^6^7^8^3).
now xor the unique elements using hash table ,It gives (1^4^2^6^7^8^3).
Now xor these two value which gives 4.
On 11/18/11, Dave
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
thanks a lot guys...
On Sep 19, 7:22 pm, Don dondod...@gmail.com wrote:
This depends on rnd being a good pseudo-random generator. I don't
suggest using the RNG built into many compilers. Instead use something
like the Mersenne Twister which produces much better results with an
extremely long
This depends on rnd being a good pseudo-random generator. I don't
suggest using the RNG built into many compilers. Instead use something
like the Mersenne Twister which produces much better results with an
extremely long period. My Random class has a gen method which
returns an integer in the
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)
See when u xor two same numbers, the result is 0.
So as mentioned in the question, all numbers occur twice, so the result will
be 0 for them and the one occuring once will be left(as 0 ^ number gives
number itself).
Hope u got
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
Oh sorry, i didnt read the question carefully:)
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
On Wed, Aug 17, 2011 at 12:34 AM, Sanjay Rajpal sanjay.raj...@live.inwrote:
See when u
See when u xor two same numbers, the result is 0.
So as mentioned in the question, all numbers occur twice, so the result will
be 0 for them and the one occuring once will be left(as 0 ^ number gives
number itself).
Hope u got it :)
Sanjay Kumar
B.Tech Final Year
Department of Computer
Thats right...by doing xor this can't be done...hey sanjay please
reconsider your answer.
On Aug 17, 2:05 pm, sukran dhawan sukrandha...@gmail.com wrote:
when u xor nos with odd number of times we will get back the same no.only
even occurences will give 0.question is to find the no with even
Yes, sry abhishek , i didnt see the question carefully.
But this can be done with hash map requiring O(n) space and O(n) time.
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National Institute of Technology Kurukshetra
Kurukshetra - 136119
Haryana, India
On Wed, Aug 17, 2011
pl give the algo
On Wed, Aug 17, 2011 at 2:50 PM, Sanjay Rajpal srn...@gmail.com wrote:
Yes, sry abhishek , i didnt see the question carefully.
But this can be done with hash map requiring O(n) space and O(n) time.
Sanjay Kumar
B.Tech Final Year
Department of Computer Engineering
National
@Raghavan: But aren't maps implemented as binary search trees? That
would make insertion and searching O(log n), and the overall operation
O(n log n).
Dave
On Aug 16, 4:08 am, Raghavan its...@gmail.com wrote:
@sukran:
If you were asking for the map based solution
space and time complexity
+1 to dave.xor is the way to go.
On Tue, Aug 16, 2011 at 7:06 PM, Dave dave_and_da...@juno.com wrote:
@Raghavan: But aren't maps implemented as binary search trees? That
would make insertion and searching O(log n), and the overall operation
O(n log n).
Dave
On Aug 16, 4:08 am,
i cudnt understand how is it done here by using xor by chen.. aftergetting F
it wud be the xor of of odd occuring elements, fine, then he wrote if(xor)A1
==0 how is this logic used??
On Wed, Aug 17, 2011 at 8:17 AM, saurabh singh saurab...@gmail.com wrote:
+1 to dave.xor is the way to
Dave tu mahan hai . . . .
-- Forwarded message --
From: Dipankar Patro dip10c...@gmail.com
Date: 14 Aug 2011 23:27
Subject: Re: [algogeeks] Re: array question
To: algogeeks@googlegroups.com
@Dave nice algo. Really like it.
So the whole complexity depends on the sorting.
On 14
thanks guys.
On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath nve...@gmail.com wrote:
Dave tu mahan hai . . . .
-- Forwarded message --
From: Dipankar Patro dip10c...@gmail.com
Date: 14 Aug 2011 23:27
Subject: Re: [algogeeks] Re: array question
To: algogeeks
23:27
Subject: Re: [algogeeks] Re: array question
To: algogeeks@googlegroups.com
@Dave nice algo. Really like it.
So the whole complexity depends on the sorting.
On 14 August 2011 22:58, Dave dave_and_da...@juno.com wrote:
@Dipankar: If extra space is not allowed, I think the optimal
@Dave nice algo. Really like it.
So the whole complexity depends on the sorting.
On 14 August 2011 22:58, Dave dave_and_da...@juno.com wrote:
@Dipankar: If extra space is not allowed, I think the optimal solution
is to sort the two arrays, which takes O(max(m log m, n log n)). Then
the
yes we can.
On Aug 3, 10:08 pm, Arshad Alam alam3...@gmail.com wrote:
can we insert 16 elements of one dimension array in 4*4 of double dimension
array?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
in my compiler its not showing any error !!
--
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/-/fXDj3Q29epwJ.
To post to this group, send email to
take a BST whose node has an element of frequency .and another array
which will store order of elements.
for each array element search BST if node already exists increase the
freq count ..other wise add that element in the order array we took
and insert new node in BST.
now , scan the order
any specific reason fr maintaining a BST...can we simply have 2 more
arrays...one dat keeps order and the oder that keeps count
correspondingly...
is a BST more efficient than an array??
On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora
vivaciousnived...@gmail.com wrote:
take a BST whose node
nivedita: wts the use to maintaining BST.. if the same purpose can be
fulfilled by an array ..
but this can be a good method if the range of numbers is pretty large.. den
making a hash count can be difficult..
On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora
vivaciousnived...@gmail.com wrote:
maintaining the bst of n element in worst case will take n square time
complexity ..do we have a better solution for worst case
On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.comwrote:
nivedita: wts the use to maintaining BST.. if the same purpose can be
fulfilled by an
i tried making a program using arrays...bt im getting segmentation
error...can anybody expalin y...
http://ideone.com/bEUUv
On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com
wrote:
@rahul- balanced BST can be maintained.to remove worst case !
@sukhmeet- i did not gt
@nivedita:can u do this in o(n) time , i suppose your algorithm takes
0(nlogn) time
On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com
wrote:
@rahul- balanced BST can be maintained.to remove worst case !
@sukhmeet- i did not gt your method completely ..u are trying to
Create a balance BST.
Maintain counter. Whenever You hit duplicate increase the counter while
inserting.
O(nlogn) for creating it and O(N) space.
Now while traverse the array.
If you find the element, then print it acco the counter value. After
printing delete it.
if not found continue traversing.
@neeraj:deleting after printing will adds to complexity..
On Sun, Jul 31, 2011 at 1:34 AM, Neeraj Gupta neeraj.gupta...@gmail.comwrote:
Create a balance BST.
Maintain counter. Whenever You hit duplicate increase the counter while
inserting.
O(nlogn) for creating it and O(N) space.
Now
ok lets think in terms of hashmap of number and frequency
we definitly have to maintain an order array .
traverse original array , we check if its present in hashmap ..if not
- 1)add it to hashmap and set frequency to 1 2)add it in order array
if yes then increment frequency by 1.
searching
Yes, i agree, it will increase the code complexity only. you can just set
the counter to -ve value only.
On Sun, Jul 31, 2011 at 1:38 AM, Kamakshii Aggarwal
kamakshi...@gmail.comwrote:
@neeraj:deleting after printing will adds to complexity..
On Sun, Jul 31, 2011 at 1:34 AM, Neeraj Gupta
@nivedita :hashing will not work if the range of nos is high
On Sun, Jul 31, 2011 at 1:40 AM, nivedita arora vivaciousnived...@gmail.com
wrote:
ok lets think in terms of hashmap of number and frequency
we definitly have to maintain an order array .
traverse original array , we check if its
that is why i gave BST algo first :)
but rahul wanted me to give O(n) algo
On Jul 31, 1:15 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@nivedita :hashing will not work if the range of nos is high
On Sun, Jul 31, 2011 at 1:40 AM, nivedita arora vivaciousnived...@gmail.com
@nivedita:ohhh :P
On Sun, Jul 31, 2011 at 1:46 AM, nivedita arora vivaciousnived...@gmail.com
wrote:
that is why i gave BST algo first :)
but rahul wanted me to give O(n) algo
On Jul 31, 1:15 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote:
@nivedita :hashing will not work if the range
@ Aditi: you forgot to initialize the arrays and elements.
Thats why the
for(i=0;ik;i++)
for(j=0;jcount[i];j++)
a[p++]=order[i];
was creating some fault while accessing one of the arrays.
I just initialized the arrays and it worked:
http://codepad.org/UO8riyjs
^^ You might want
@piyush: Just curious, how exactly can a stack be used in this
problem?
On Jul 26, 5:00 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Sorry for the above mistakeits not O(n)
On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
Use stack
On Tue, Jul
@ankit: you are right...sorry about the error
On Jul 26, 5:11 pm, ankit sambyal ankitsamb...@gmail.com wrote:
The O/P of ur example should be 2,2,1,1,1,-1,-1
or am I getting it wrong ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To
@Piyush, using stack i guess it can be done in O(n)
On Tue, Jul 26, 2011 at 5:42 PM, Shikhar shikharko...@gmail.com wrote:
@ankit: you are right...sorry about the error
On Jul 26, 5:11 pm, ankit sambyal ankitsamb...@gmail.com wrote:
The O/P of ur example should be 2,2,1,1,1,-1,-1
or am I
a crude algo,
for(i=end to start)
{
while(!stk.empty())
{
if(arr[i]arr[stk.top])
pop();
else
break;
}
if(!stk.empty())
l = arr.length-1;
else
l = stk.top;
output[i]=l-i-1;
stk.puch(i);
}
This will be O(n). Correct me I am wrong anywhere..
On Tue, Jul 26, 2011 at 5:49 PM,
@Akshata : Plz explain ur algo... Its not clear.
Like in the first iteration,
else
l = stk.top;
is getting executed. but stack is empty, so how r u assigning value to l
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
sorry for the typo ankit, its
if(stk.empty())
l = arr.length-1;
else
l = stk.top;
On Tue, Jul 26, 2011 at 6:19 PM, ankit sambyal ankitsamb...@gmail.comwrote:
@Akshata : Plz explain ur algo... Its not clear.
Like in the first iteration,
else
l = stk.top;
is getting executed. but
@Shikhar
1) Push the first element to stack.
2) for i = 1 to n-1
a) temp =a[i]
b) while(stack not empty)
int x = pop(stack)
if(xtemp) print(temp);
else
push(x,stack)
break;
c) push(temp,stack)
3) After the
Try the Array Section on geeksforgeeks.org obviously without looking at the
solutions.
--
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/-/XsqWbXVJ8CkJ.
To post
try rotaion of matrix by 90, 180, 270 and 360 degree in both clockwise and
anti clockwise directand try printing matirx in spiral order...
On Sat, Jul 9, 2011 at 12:08 AM, Nitish Garg nitishgarg1...@gmail.comwrote:
Try the Array Section on geeksforgeeks.org obviously without looking at
the
due to constant folding
On Jul 4, 6:54 am, Navneet Gupta navneetn...@gmail.com wrote:
If you can, refer to Constants chapter in Bruce Eckel. He he smartly
explained how const are different for C C++.
The e-book is free to download from net.
On Mon, Jul 4, 2011 at 2:50 AM, Gene
Why do bicycles have 2 wheels and tricycles 3? The designers made
them that way.
So you're probably asking why they were designed that way.
C++ came after C. In general C++ seeks to de-emphasize use of the pre-
processor because macro substitution is generally considered to make
maintenance
If you can, refer to Constants chapter in Bruce Eckel. He he smartly
explained how const are different for C C++.
The e-book is free to download from net.
On Mon, Jul 4, 2011 at 2:50 AM, Gene gene.ress...@gmail.com wrote:
Why do bicycles have 2 wheels and tricycles 3? The designers made
them
@ross: I couldn't get reddy's solution. Please explain.
On Sun, Jun 5, 2011 at 10:50 PM, Deepak Jha deepak.127.0@gmail.comwrote:
the below solution should work given the input array is sorted ( I am
assuming ascending order)
void rearrangeArray(int[] a, int[] b){
int m = a.length;
int
@aakash Johari:
Let a and b be the 2 arrays.
At each stage of the process, if an element of A is greater than B,
then swap the largest element of A with the smallest element of B
and adjust pointers.
A : 2 4 15 12
B : 0.2 1 33 44
Now, 20, therefore swap 0 with 12..
Every step of the process,
the below solution should work given the input array is sorted ( I am
assuming ascending order)
void rearrangeArray(int[] a, int[] b){
int m = a.length;
int n = b.length;
int i = m - 1;
int j = 0;
while((i =0) (j = n-1)){
if(a[i] b[j]){
int temp = a[i];
a[i] = b[j];
b[j] = temp;
}
i--;
j++;
}
}
i think solution would be like this
eg:
A : 1 2 3 B: 0 1.5 4 5 9
Output:
A can contain any combination of nos 0,1,1.5
and B should contain 2 3 4 5 9 (in any order.)
this example is given by ROSS itself.
so sravanreddy solution is right , correct me if i'm wrong.
On Jun 3, 8:07 pm, bittu
Hi Rohit all,
Sorry that there was a small typo in the 'n' 'm' texts.
The example given by me is anyway the correct one.
Sravan Reddy's solution worked fine.
On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote:
i think solution would be like this
eg:
A : 1 2 3 B: 0 1.5 4 5 9
Output:
A
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so that array A can hold m
smallest elements then
Please try this solution. And tell if it fails at any case. If it works
fine, I will tell the logic.
#include stdio.h
#include stdlib.h
void merge(int *a, int m, int *b, int n)
{
int i, j, k;
int t;
i = j = 0;
k = -1;
while ( i m a[i] b[j] ) {
i++;
it can be done in O(m) . Use something like binary search .
code is here ...
#includestdio.h
void splitMN(int a[],int m , int b[], int n){
int al = 0 , bl = 0 ;
int ah = m-1 , bh = n-1 ;
int ai = (ah+al+1)/2;
int bi = (bh+bl+1)/2;
while(ai+bi!=m){
printf(Enter ai
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
You received this
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
@sravanreddy: it won't work. Try 3,91,9 and 90,1,8,2,5 . correct me
if i m wrong.
Thanks,
Ankit Sambyal
On Sat, May 28, 2011 at 9:16 PM, ross jagadish1...@gmail.com wrote:
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
@Ankit, The input should be 2 sorted arrays
Thanks,
Immanuel
On Sun, May 29, 2011 at 10:48 AM, ankit sambyal ankitsamb...@gmail.comwrote:
@sravanreddy: it won't work. Try 3,91,9 and 90,1,8,2,5 . correct
me if i m wrong.
Thanks,
Ankit Sambyal
On Sat, May 28, 2011 at 9:16 PM, ross
Oh I didn't read the question properly, Thanks for pointing out...
On Sat, May 28, 2011 at 10:28 PM, immanuel kingston
kingston.imman...@gmail.com wrote:
@Ankit, The input should be 2 sorted arrays
Thanks,
Immanuel
On Sun, May 29, 2011 at 10:48 AM, ankit sambyal
@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
@Dave: Can you please explain it? I am not getting you.
--
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
@all after 32 Message Discussion I know Everyone is looking for O(N)
solution well it seems odd how we can search an element in a O(m*n)
matrix in O(n) but answer of this question is given already in the
question that all row column are sorted so why O(n) solution
exist it really matters
@Mannu. You said that the complexity of the counting sort is O(n).
Doesn't the complexity depends on the data? In particular, I'm asking
you to explain more completely how you obtain O(n) complexity with the
counting sort on a particular data set where the range of the data
depends on n. Can you
I can think of 2 methods if Hashing is not allowed.
1. Plain comparison of every element with an other element, which takes
O(n2)
2. We can sort the array, and the best we could achieve is O(nlogn) after
that use simple comparision,
like the code here : http://codepad.org/RtRbnyAN; Overall
1 - 100 of 234 matches
Mail list logo
