@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote:
On 24 lis, 07:02, kumar raja rajkumar.cs...@gmail.com wrote:
In the given array all the elements occur single time except one element
which occurs 2 times find it
Given an unsorted array arr[0..n-1] of size n, find the minimum length
subarray arr[s..e] such that sorting this subarray makes the whole
array sorted.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
http://www.geeksforgeeks.org/archives/8858
On 24 November 2011 01:06, Ankuj Gupta ankuj2...@gmail.com wrote:
Given an unsorted array arr[0..n-1] of size n, find the minimum length
subarray arr[s..e] such that sorting this subarray makes the whole
array sorted.
--
You received this message
char arr[] = {'a', 'b', 'e', 'f', 'd', 'g', 'h', 'i'};
calculate the point where array is not sorted , in this case arr[4] =
'd'
calulate k in array[5..n] such that k 4 arr[k] d , take the min =
min{ arr[k] }
same thing for max from reverse
use quick /selection sort to identify the correct
I have an O(n) space and time solution by using hashing . Firstly,
make a hash table by using a hash function for each of the number in
the array. After that, go through the hash table to see whether there
are any repetitions for the same entry.
--
You received this message because you are
hashing is not that simple, can you tell your hash function ?
On Thu, Nov 24, 2011 at 6:26 PM, ravu sairam ravu...@gmail.com wrote:
I have an O(n) space and time solution by using hashing . Firstly,
make a hash table by using a hash function for each of the number in
the array. After that, go
@ravu sairam:
Suppose the hashing is banned ,now what is ur solution???
Hashing is quite theoretical concept with time complexity O(1).
But it will not be the case every time.so suggest some other better
solution
I used to thought of using count array ,but again its size is not O(n), its
size
find it in O(n) time and O(1) space,
are you sure that it is possible to do it in O(n) time ?
On Thu, Nov 24, 2011 at 6:59 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@ravu sairam:
Suppose the hashing is banned ,now what is ur solution???
Hashing is quite theoretical concept with time
@shady : i am not sure , if u can do it with O(n) space as well it is fine
for me . but once try whether it is possible in O(1) space.
On 24 November 2011 05:42, shady sinv...@gmail.com wrote:
find it in O(n) time and O(1) space,
are you sure that it is possible to do it in O(n) time ?
On
i also doubt about the time and space complexity of the problem, i has been
asked a number of times with these constraints but never been answered the
required, as far as i remember the best solution to this problem that has
been discussed so far is using hashing and that too theoretically having
i don't think there is an O(n) time solution for this... bcoz there are no
constraints on the values, and on the number of values in the array.
On Thu, Nov 24, 2011 at 7:15 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@shady : i am not sure , if u can do it with O(n) space as well it is fine
Finding duplicates in a multiset is a pretty standard problem. I've
only ever heard of two solutions, and it's unlikely there are others.
One is to sort, which will place duplicates adjacent to each other, so
you can find them by comparing a[i] with a[i+i] for all I. This
algorithm is O(sorting
http://en.wikipedia.org/wiki/XOR_linked_list
In this link i have seen about Xor linked list ,but my doubt is how will u
perform xor on Address of nodes.
I have tried to perform xor on addresses of two values ,so how is it
possible to use that technique.
Also tell me whether there are any extra
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not get u, once explain with example...
On 23 November 2011 23:47, kunzmilan kunzmi...@atlas.cz wrote:
Matrix M
0 1 0
0 1 0
1 0 0
multiplied with M(T)
0 0 1
1 1 0
0 0 0
gives
1 0 0
0 2 0
0 0 0.
On its diagonal
address can be xored easily with xor operator...
http://www.geeksforgeeks.org/archives/12367
On Thu, Nov 24, 2011 at 7:37 PM, kumar raja rajkumar.cs...@gmail.comwrote:
http://en.wikipedia.org/wiki/XOR_linked_list
In this link i have seen about Xor linked list ,but my doubt is how will u
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please elaborate it...
On 24 November 2011 06:15, kunzmilan kunzmi...@atlas.cz wrote:
On 24 lis, 09:09, kumar raja rajkumar.cs...@gmail.com wrote:
@kunzmilan : i did not
go to link i said..n at bottom u can find sum programs that are user
responshop it helps
On Thu, Nov 24, 2011 at 8:45 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@rahul:
when i tried the following i got an error
int a=3,b=2;
printf(%p, (a)^(b));
On 24 November 2011 06:28,
Can you please elaborate...
On Thu, Nov 24, 2011 at 12:14 AM, atul anand atul.87fri...@gmail.comwrote:
yes levenshtein distance and BK tree can be used to solve this.
where edge weight between nodes is equal to levenshtein distance.
On Wed, Nov 23, 2011 at 7:14 PM, abhishek kumar
http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees
this would help.
On Thu, Nov 24, 2011 at 9:49 PM, Vijay Meena vijay...@gmail.com wrote:
Can you please elaborate...
On Thu, Nov 24, 2011 at 12:14 AM, atul anand atul.87fri...@gmail.comwrote:
yes levenshtein distance and
Struct tuple
{int s;int e;}
tuple findsubarray(Array input)
{
int i=0, j=input.length()-1;
while(input[i] input[i+1])
i++;
if(i==j) return NULL // array already sorted
while(input[j-1] input[j])
j--;
// now the subarrays from 0 to i is sorted and j to end is sorted.
int min =
Please explain what do you mean by 'path between x and z'.
On Wed, Nov 23, 2011 at 11:46 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
There is a binary tree (Not a BST) in which you are given three nodes
X,Y, and Z .Write a function which finds whether y lies in the path b/
w x and z.
--
You
@Gene - nice, correct and elegant algorithm.
On Wed, Nov 23, 2011 at 9:33 PM, Ankur Garg ankurga...@gmail.com wrote:
@Gene
Your algo is also right...Just that I followed techcoders logic and coded
the same...pair I used to map the index of the element ..But urs working
fine too :)
On
This is very language-dependent. In assembly it's no problem at all!
In C you must coerce to an integer type where xor is possible.
The portable way to make this work including 64-bit systems is to use
type uintptr_t from stdint.h. Not all compilers have this.
Perhaps the next best hing to try
struct abc
{
int g;
float f;
double gj;
};
like in this int takes 4 bytes and we want align in 8 bytes so i wana know
that whether the float should put with int as 4 bytes are there to complete
8 or float should be int+4 bytes padding and then store the float..
acc to o/p float is
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can u please maintain the clarity ??
How did u find the M
if the list is 4 2 8 9 5 1 9 how M looks like ?? please
As it seems to me this can be solved like this
Find LCA(Least common ancestor) of node x and z .. See if it equals y or
not . If not recursively search for y in left and right subtree of LCA ..If
you find y in the descendents of LCA answer is true else its false .
This method will give perfect
@Anup:
Atleast u tell me how the M has formed???
On 24 November 2011 11:21, Anup Ghatage ghat...@gmail.com wrote:
@kunzmilan
Nice idea, how do you decide the row-size or column-size of the matrix?
On Thu, Nov 24, 2011 at 8:00 PM, kumar raja rajkumar.cs...@gmail.comwrote:
@kunzmilan :
Can
This approach would fail in certain cases :P..in fact lot many cases :D..It
needs to be modified using space
The thing is while calculating LCA we must also store the path in an Array
or vector and then Iterate over its elements to check if match occurs.
Cant think of O(1) solution though :(
^^+1..how matrix formed ??
But as Gene said we can use a set to store all the unique elements
Now we xor all the set elements and then xor them with the elements of the
array . This wud give us the repeating element as all the elements coming
once will be 0(xored twice) and repeating element wud
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
@Gene : Are you sure, when you pop element from stack it will not be next
smaller element to remaining elements in the array(Input)?? I think this is
not gonna work...
On Wed, Nov 23, 2011 at 7:04 PM, Gene gene.ress...@gmail.com wrote:
Sorry I forgot to initialize p. It's fixed below.
On Nov
31 matches
Mail list logo
