1,6,3,4,6,5,6,2,6,6
or
1,2,3,6,4,6,5,6,6,6
lovely...
Use a two-step process. First, check for a repeated number in the
first 4 elements. If none is found, then there are at least n/2-1
occurrences of the repeated elements in the last n-3 elements, meaning
that there must be at least two
I thought again on this, i think we have made a simple problem quite
complicated
if a number is half times in a list, that implies that either it is
repeated alternately otherwise adjacent somewhere else
so if this is repeating alternatively that in first 4 occurrence, we should
have this at
point to note abt anand's code
reason why it does not work
a] when u r doing xor from index 1 to index n( take two cases that n/2
is od or even)
resulting xor will be an xor impression of non repeating number +
either 0 or 1 time the repeating number
now you start xoring again from index
@Anish: Does it work on 1,2,3,1?
Dave
On Aug 7, 2:04 am, Ashish Goel ashg...@gmail.com wrote:
I thought again on this, i think we have made a simple problem quite
complicated
if a number is half times in a list, that implies that either it is
repeated alternately otherwise adjacent
Hi,
I am looking for an algorithm that given a set expression, will
compute the minimum form of the set expression. It is sort of the
boolean expression simplification, but for sets.
For example, if the input is
((A union B) intersection C) union ((A union B) intersection D)
we can simplify this
Observation:
Following is the sequence of indices which we want to swap:
(2,n+1)
(3,n+1)
(4,n+2)
(5,n+1)
(6,n+3)
(7,n+2)
(8,n+4)
(9,n+3)
Hence, for even indices we swap (k,n + k/2) and for odd indices, we swap(k,
n + k/2-1).
This is O(n). and constant space.
for(k=1;k=2*n;k++) {
if(k%2==0) {
@Amir: how you have found this relation
dp[i][j]=dp[i-1][j]+dp[i][j-1]
i am not able to understand it. Plz explain it.
thanx
On Tue, Jul 13, 2010 at 3:39 AM, Amir hossein Shahriari
amir.hossein.shahri...@gmail.com wrote:
dp[i][j] is the number of strings that have i As and j Bs
we can do one thing. compare first element with all others. if it matches
with any of them, we have found our number, else leave the first number and
now the required number is available (n/2)+1 times in the rest of the array,
which can be found in O(n)
--
You received this message because you
Doesn't mapping union to or and intersection to and map the
set expression minimization problem to a boolean expression
minimization problem? Am I missing something?
Dave
On Aug 7, 1:56 am, Harsha Nagesh harshasnag...@gmail.com wrote:
Hi,
I am looking for an algorithm that given a set
Already posted
compare pair wise i.e a[0] and a[1]a[2] and a[3]..
leave out last 4 elements...
repeated element can be found in 3 comparison for these 3 elements...
total no of comparison in worst case
(n/2+1)
Thanks
Pramod Negi
On Sat, Aug 7, 2010 at 7:14 PM, ankur bhardwaj
@Nikhil Jindal
check your fromula for indices when k = 3
it is k/2 - 1 = 0
thus it will give swap(3,n).
On Sat, Aug 7, 2010 at 5:37 PM, Nikhil Jindal fundoon...@yahoo.co.inwrote:
Observation:
Following is the sequence of indices which we want to swap:
(2,n+1)
(3,n+1)
(4,n+2)
I guess
a, x, y, a
is the only case where anish's algo fails.. because in every other case the
repeated digit will either be consecutive or alternative.. So, it will be
better to pre-check this condition and apply the above algo.. Please do give
any suitable example to contradict.
regards
On
@priyanka i agree with u... but wat i thot was if v had a tree with
parent pointers...we can have one pointer at the left most and another at
the rightmost subtree respectivelyand move along the pointers..
I need ur discussion on thisi think the implementation wud be
is there a way to apply a binary search on a sorted array...with a
catch... the array is rotated k times clockwise
Example...4,5,1,2,3...
I heard a binary search is possible..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
14 matches
Mail list logo
