[algogeeks] Re: Finding the repeated element
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 are numbers of repeated elements. kunzmilan 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 in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding the repeated element
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 in O(n) time and O(1) space. e.g. 2 3 4 9 3 7 output :3 If such a solution exist can we extend the logic to find All the repeated elements in an array in O(n) time and O(1) space -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in Write the list in the form of a matrix M, e.g. 0 1 0 0... 0 0 1 0... 0 0 0 1... ..etc., and its quadratic form M(T)M shows, how many times each element repeats. kunzmilan -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Divide 2 nos. without DIVISON
On 22 kvě, 08:40, punnu punnu.gino...@gmail.com wrote: Given 2 nos. we need to divide them without performing divison. Please give a better solution than subtracting the nos. again and again. Try to multiply the smaler number and by a suitable number, subtract the product, compare, and repeat adding zeroes, if necessary. kunzmilan -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: unique number in an array
Write the array as a vector string S, eg
(1,0,0,0...)
(0,0,1,0...)
(0,0,0,1...)
etc.
Find the quadratic form S^T.S. On its diagonal, occurences of all
numbers are counted.
kunzmilan
On 13 čvn, 20:44, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
give an algo to find a unique number in an array
for eg a[]={1,3,4,1,4,5,6,1,5}
here 3 is the unique number as it occur only once... moreover array contains
only 1 unique number
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: An interview question
On Dec 17, 12:49 pm, vicky mehta...@gmail.com wrote: given a graph G(V,E) and a source vertex, v. no. of vetices n, and edges e. you have to find all different paths from vertex v to some vertex N, having exactly i(1in) edges. v,N,i will be given by the user. provide an algorithm for it. The adjacency matrix A shows all paths between vertices of lenghts 1. Its powers A^n shows all paths between vertices ij of length n. kunzmilan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: How to find number of Cycles in a Graph...
On 21 říj, 12:15, mithun mithunsi...@gmail.com wrote: Given a graph can anyone suggest me good algorithm to find out Number of Cycles in a Graph.. -Thanks Mithun Find polynomials of its adjacency matrix. The resulting polynomial consists from loop, edge, cycle and edge-cycle polynomials. kunzmilan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: 100!
On 10 říj, 21:54, vicky mehta...@gmail.com wrote: find some of all the digits in number-100! Any n!, n 100, has at least 22 zeroes on its end. kunzmilan --~--~-~--~~~---~--~~ 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, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Traversing a binary tree from bottom to top
On 2 říj, 16:07, Manisha pgo...@gmail.com wrote: Traversing a binary tree from bottom to top The only way I could think of is: Traverse the binary tree from top to bottom, level by level with the help of queue. For a tree like: a b c d e g The Queue will be something like: a b c d e g Now de-queue the element one be one from queue and push on stack. Pop the stack one by one to get deserved output: g e d c b a This will take o(n) space and o(n)time. Is there any better way of doing it? There exists the Pruefer algorithm for trees, based on their pruning, expressing trees as strings of symbols. It is valid also for binary trees. kunzmilan --~--~-~--~~~---~--~~ 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, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find triangle in a graph
On 6 zář, 11:28, ankur aggarwal ankur.mast@gmail.com wrote: google question : find triangle in a graph Given an undirected graph, design a O(V+E) algo to detect whether there is a triangle in the graph ot not. This problem can be solved by finding polynomial of the graph. kunzmilan --~--~-~--~~~---~--~~ 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, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: how to select a set of strings that are most dissimilar?
On 10 Dub, 07:45, Jing jingai...@gmail.com wrote: Hey all, My problem is as follows: 1) I have N strings and all strings has the same length L. 2) To be simplified, each string is composed by english letters. How to select a set of M (M N) strings that are most dissimilar? My questions are as follows: 1) For any two strings, we can calculate the edition distance as the dissimilarity. If there are more than 2, say M, strings, how to characterize the dissimilarity of the whole set? 2) If the first question is well addressed, how to select the best M string so that the dissimilarity metric is maximized? Many thanks! I appreaciate any of your comments! There are several solutions of your problem: 1) Simple countings. 2) Both strings can be compared as oriented indexed multigraphs a b q a 3) distances between symbols (mixing distances) can be determined, they should correspond to negative binomial distribution. kunzmilan --~--~-~--~~~---~--~~ 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, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Enumerating trees
On May 13, 2:20 am, brunotavila [EMAIL PROTECTED] wrote: Hi people, How to calculate the number of binary trees that are subgraphs of a given connected, undirected, unweighted and simple (no parallel edges nor loops) graph? Bruno This problem was studied in chemistry, at first by Harry Wiener. And it is known as Wiener number. In chemistry, more important that the number of binary trees is their total length, sum of distances between vertices. kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Plannar graph
On 4 Dub, 02:14, Douglas Diniz [EMAIL PROTECTED] wrote: A triangle is a planar graph with vertix less than 5 degree. A vertice with n other vertices connect to it (so have degree n) is a planar graph. So we may have planar graphs where all vertex has degree less than 5, and planar graphs with n vertex with degree more than 5. On Thu, Apr 3, 2008 at 8:01 PM, Karthik Singaram Lakshmanan [EMAIL PROTECTED] wrote: Correct that to : There exists at least one vertex of degree at most 5 You all are right, when planarity is defined as crossing of edges on a graph. But, objects can be linear, planar, and generally n-dimensional. Even graphs have this property. K(4) can be a square with both diagonals, a triangle with axes ending in its center, and as a tetrahedron. These forms have different distance matrices with different eigenvalues. kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Plannar graph
On 24 Bře, 11:18, nima aghdaie [EMAIL PROTECTED] wrote: A graph is planar iff it does not contain K5 and K3,3 . read chapter 6 (Planar Graphs) from Introduction to Graph Theory, Douglas B. West Planarity can be defined differently. Graph K(4) Can be drawn without crossing arcs. Newertheless, as tetrahedron, it is not planar. To both forms, different distance matrices belong. kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Plannar graph
On 17 Bře, 10:38, sp1 [EMAIL PROTECTED] wrote: How to test an given graph is plannar? The answer gives its distance matrix. When distances between vertices of the graph are squared, the distance matrix of a plannar graph has only 4 nonzero eigenvalues. kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: factorial
On 13 Ún, 03:17, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: how will u find the number of digits in the factorial of a number without finding the factorial?? Try Stirling formula. Rougly nlogn. kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Testing if 3 points form a triangle
On Jun 4, 10:56 pm, Feng [EMAIL PROTECTED] wrote: Hi Kunzmilan, thanks for your idea of using distance matrices. But one of my friends came up with a seemly counter-example: Take 3 collinear points in 2D: (0,0), (1,0), (2,0). The distance matrix is: 0 1 4 1 0 1 4 1 0, whose eigenvalues are -4, -0.4495, 4.4495. It means that they form a 2D shape, but they make a line (1D shape). Is there anything wrong in it? I tried to answer the question five days ago, but my answer did not appeared. The eigenvalue a at straight chains is produced by the reflexion plane (elements of the of the eigenvector are symmetrical to the center of the chain) and its rotation tensor b = (a + W/2) = [\sum d^4 - 3/4 W^2]^1/2, where W is The Wiener index (half of the sum of distance matrix elements. The sum of squared eigenvalues must be equal to the trace of the squared matrix. Solving the quadratic equation gives four eigenvalues (including zero) as W/2 +/- (b or W/2). kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Derangements
Write permutations as matrices, e.g. (0,1,0,0) (0,0,1,0) (0,0,0,1) (1,0,0,0). You need only one operation to get 1,2,3,4. kunzmilan --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
