@Anand :Your approach will turn out very crude if elements are something
like 1000, 2000
keeping an array i.e count[1000] is not feasible. I think souravsain's
approach is better.
On Mon, Jun 7, 2010 at 3:57 AM, Anand anandut2...@gmail.com wrote:
Here is my approch which runs in O(n).
The link http://geeksforgeeks.org/?p=1488 has many different solutions and
implementation of hashing method.
On Mon, Jun 7, 2010 at 12:59 AM, Raj N rajn...@gmail.com wrote:
@Anand :Your approach will turn out very crude if elements are something
like 1000, 2000
keeping an array i.e
@souravsain :Your approach works really well..
Here is the Implementation:
http://codepad.org/ricAcQtu
On Sun, Jun 6, 2010 at 11:40 AM, souravsain souravs...@gmail.com wrote:
@divya:go through the elements and keep inserting them in a BST. While
inserting if elements already exists in BST,
@Anand
Depending upon the sequence of data in the input, an insertion/search into
the (unbalanced) BST will take O(n) time causing the overall complexity to
shoot up to O(n^2) for each element counted once. Sourav's approach requires
a balanced binary search tree.
@Divya..
If you know something
@sharad: Your code seems will seem to give output 12,3,4 and not
12,3,3,3,4. It semes from the original description of the problem that
you also need to keep count of frequency of occurance of items in the
map.
Secondly, you have iterated through the map and got the elemenst in
same order as you
output willl be 12 12 5 6 6
On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote:
@divya: Does your problem require the output to be sorted also? What
will be the output required if inout is 12,5,6,12,6? Will it be
12,12,6,6,5 or 12,12,5,6,6,?
Sain
On Jun 6, 12:01 am, divya
@divya:go through the elements and keep inserting them in a BST. While
inserting if elements already exists in BST, increase its frequency
(Node of BST has element a nd frequency). Also if elemengs is newly
inserted then also place it in a seperate array. So this array (say
Array M) will become
Here is my approch which runs in O(n).
http://codepad.org/d3pzYQtW
http://codepad.org/d3pzYQtW
On Sun, Jun 6, 2010 at 7:47 AM, divya jain sweetdivya@gmail.com wrote:
output willl be 12 12 5 6 6
On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote:
@divya: Does your problem
hi hw about this
for(i=0;in;++i)
{
if(a[a[i]]!=a[i]flag==0)
{
a[a[i]]=a[i];
flag=1;
}
else
{
couta[i] is duplicate element;
}
}
if range is high we hash take mod of that elemnt with big value and hash it
in same array and check for collision
On Mon, Oct 5, 2009 at 10:09 AM, Amit Chandak
Use a bit-field of M bits to keep track of the presence of X..X+M-1. We can
do 2^32/M passes (if the elements are 32-bit size) to check for numbers in a
range. Depending on the memory footprint and speed the app would want we can
find a soft spot for X.
On Sun, Oct 4, 2009 at 9:39 PM, Amit
If the array is sorted, doing xor of a[n] and a[n+] will result 0 for
duplicate no.
--Bala
On Mon, Oct 5, 2009 at 7:06 PM, Ramaswamy R ramaswam...@gmail.com wrote:
Use a bit-field of M bits to keep track of the presence of X..X+M-1. We can
do 2^32/M passes (if the elements are 32-bit size) to
Hi James
On Nov 26, 3:52 pm, James Fang [EMAIL PROTECTED] wrote:
The negative pair value can be workarounded by normalizing the
pair to be in the [0,MAX_INT] range.
This can be achieved by adding MAX_INT/2 to the pair before
addressing the one bit in the bit map.
I don't
:[EMAIL PROTECTED] MJ
Date: 2007年11月23日 18:25
To: Algorithm Geeks
Subject: [algogeeks] Re: Re: [algogeeks] Re: Array of integers
Hi James,
As per your solution the variable pair can go negative and if Array[i]
X,
and in that case you can not use bitmap[pair] which will give an
exception as we can
], the
bitmap
method can be better applied.
Best Regards,
James Fang
-邮件原件-
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
Dave
发送时间: 2007年11月21日 星期三 2:29
收件人: Algorithm Geeks
主题: [algogeeks] Re: Array of integers
Want to try again
in the array have a stricted range, like [-x,y], the bitmap
method can be better applied.
Best Regards,
James Fang
-邮件原件-
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
Dave
发送时间: 2007年11月21日 星期三 2:29
收件人: Algorithm Geeks
主题: [algogeeks] Re: Array of integers
: 2007年11月21日 星期三 2:29
收件人: Algorithm Geeks
主题: [algogeeks] Re: Array of integers
Want to try again?
Consider the case where array = {2,3} and X = 5.
First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so
you mark bitmap[3].
Then you have pair = 5 - 3 = 2 and noet
in the array have a stricted range, like [-x,y], the bitmap
method can be better applied.
Best Regards,
James Fang
-邮件原件-
发件人: algogeeks@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
Dave
发送时间: 2007年11月21日 星期三 2:29
收件人: Algorithm Geeks
主题: [algogeeks] Re: Array of integers
Want
You can acheive O(n) by using a bitmap.
the pseudo code can be described below:
for i=0 to N
pair = X - array[i];
if( bitmap[pair] == marked )
found the answer!
else
mark bitmap[pair]
the bitmap can be an array in the RAM or external disk,
Want to try again?
Consider the case where array = {2,3} and X = 5.
First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so
you mark bitmap[3].
Then you have pair = 5 - 3 = 2 and noet that bitmap[2] != marked, so
you mark bitmap[2].
Presumably, at this point, since you have
@googlegroups.com [mailto:[EMAIL PROTECTED] 代表
Dave
发送时间: 2007年11月21日 星期三 2:29
收件人: Algorithm Geeks
主题: [algogeeks] Re: Array of integers
Want to try again?
Consider the case where array = {2,3} and X = 5.
First you have pair = 5 - 2 = 3 and note that bitmap[3] != marked, so
you mark bitmap[3].
Then you
can find in O(n) if array is sorted
On Nov 18, 2007 9:13 AM, dor [EMAIL PROTECTED] wrote:
You can do it in O(n log(n)) (without extra space). If you can afford
O(T) extra space (where T is the largest number in the array, in
absolute value), you can do it in O(n).
On Nov 17, 3:42 pm,
you can do it O(n) time if the input array is sorted.
Find the min and max value of the array and then decide how many
number can be eliminated based if they are greater than X.
This problem get complecated if we consider the integers are +ve as
well as -Ve intergers in an array.
But any way
You can do it in O(n log(n)) (without extra space). If you can afford
O(T) extra space (where T is the largest number in the array, in
absolute value), you can do it in O(n).
On Nov 17, 3:42 pm, geekko [EMAIL PROTECTED] wrote:
Suppose that you have an array of integers. Given a number X are
A simple modification to quicksort will do the trick !
On 11/13/07, geekko [EMAIL PROTECTED] wrote:
you are given an array of integers containing only 0s and 1s. You have
to place all the 0s in even positions and 1s in odd position. And if
suppose, no. of 0s exceeds no. of 1s or vice versa
Can you explain the modification?
--~--~-~--~~~---~--~~
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
@Dave,
*Otherwise, set the even position to 0 and the odd position to 1.*
I think your solution might be inserting 0's and 1's into the array from
nowhere (thus filling the whole array with alternating 0's and 1's up to the
given size !). The question is to re-arrange existing elements in the
Thank you, I understood the question wrong. I thought if the # of 0's
or #1's exceeded each other, the whole array would be untouched. So i
couldn't solve it in one pass.
On 13 Kasım, 16:15, Dave [EMAIL PROTECTED] wrote:
The following algorithm examine the contents of each element of the
array
No. At step 6, we have found a 1 in an even spot and a 0 in an odd
spot, so we switch them. Switching a 1 and a 0 simply means storing 0
where the 1 was and storing 1 where the 0 was; there is no need to use
the usual code to interchange two values.
Dave
On Nov 13, 8:37 am, Vikram Venkatesan
@Dave,
Ya. You are right. I think i overlooked your solution. The step 'set the
even position to 0...' sounded like, setting 0 and 1 directly :-)
Thanks,
Vikram
On 11/13/07, Dave [EMAIL PROTECTED] wrote:
No. At step 6, we have found a 1 in an even spot and a 0 in an odd
spot, so we
You could use a B-Tree or even a simple binary tree to index into the
array, but the space will be doubled (it is justified if you store
some other object in the array other than integers).
On 11/17/06, Nik [EMAIL PROTECTED] wrote:
Hi,
I have an array in which elements are present .
The
The advantage of using a list is to delete and element it does that
after a search in O(1) where as in an array we have to push all the
elements after that deleted element one position backward. Same case
with sorted insertion in an array.
Thanks,
ManuOn 5/15/06, Kapil [EMAIL PROTECTED] wrote:
Ok,
but for non negative values it should work.
Gene wrote:
This doesn't work in many cases. Consider
n = 1, N = -1, a[0] = -1 . (Algorithm says no, subseq exists.)
Or a more interesting example,
n = 4, N = 2, a = [1, -2, 5, -2] (Again alg says no, subseq exists.)
meke a corresponding cumulative sums array..
where S[i]= Summation(a[0] ... a[i])
Sum of subseq. [i..j]= S[j]-S[i-1]
check all i,j pairs
but this is O(n^2).. may be a better exists
--~--~-~--~~~---~--~~
You received this message because you are subscribed to
Daniel Etzold wrote:
A consecutive series in the array? Is this really what you
are looking for?
input: N, a[0..n-1]
l=r=c=0
while r n c N do
while c N r n do
c = c + a[r]
r = r + 1
od
while c N do
c = c - a[l]
l = l + 1
od
od
if c == N
201 - 234 of 234 matches
Mail list logo
