anujkaliaiitd
BAN USERThis soution is O(m*(m+n)) because you are doing m BFSes. Read my comment above for an O(m+n) solution.
- anujkaliaiitd July 15, 2012I didn't understand your question. Implementing a tree given an edge list should not be difficult.
- anujkaliaiitd July 15, 2012There are 2 things to explain:
1) How is it equivalent to checking whether the graph is bipartite.
2) How to check if a graph is Bipartite.
Here, for every i, you have to compute 2 subarray sums: [0, i-1] and [i+1, N-1]. This can be done by maintaining a sum[] array where sum[i] is the sum of the array from 0 to i (inclusive).
- anujkaliaiitd July 15, 2012This is the problem of determining whether a graph is Bipartite or not and can be done using BFS on the graph.
- anujkaliaiitd July 15, 2012Let us define the notion of 'root' and 'parent' on the tree. Let the root of the tree be 'r'.
Suppose that for every node 'x', we have computed the total weight of the subtree rooted at 'x' (this includes the weight of 'x'). Let us call this sum: S(x).
Then for every edge (u,v) in the tree, where 'u' is the parent of 'v', the sums of the 2 trees formed on removing edge (u,v) are S(v) and S(r) - S(v). In this way, we can iterate over all the edges and return the minimum possible difference.
Time complexity: O(N), space O(N).
is there some site where you can test code for these problems?
- anujkaliaiitd July 15, 2012Here's something complicated, but its O(N):
Construct 10 buckets (LinkedLists) where bucket i contains all numbers which contain digit i. This step is Space: O(N), time O(N).
Let us call the answer "count".
Now, for bucket i, i varies from 0 to 9:
Add bucket[i].size()*(bucket[i].size()-1)/2 to count. This is for the number of friendly pairs, which are friendly because they contain digit i. Now we need to remove pairs which have been counted earlier because they were friendly due to some digit j < i.
Create an array C[] of size i where C[j] denotes the count of numbers in this bucket (bucket[i]) whose MINIMUM digit is j.
Subtract C[j]*(C[j]-1)/2 from count, j varies from 0 to i-1.
Return count.
Its O(N) time and space.
yes, but this is not the place:
http : / / www . facebook . com / beanuj
Start 1st stack from left, 3rd stack from right and 2nd stack from the middle. While doing operations on the stacks, we will try to maintain the invariant: the second stack occupies a contiguous chunk b/w the left chunk and the right chunk, and the 2 empty spaces b/w these 3 chunks are of equal size (or differ by atmost 1).
For example, here's a valid configuration of the array (*s denote empty locations):
{1,2,2,3,4,*,*,*,2,3,4,*,*,*,*,1,4}. And here's an invalid configuration: {1,2,3,4,5,*,2,1,3,*,*,*,1}.
If the invariant is maintained, whenever any 2 stacks meet, we have exactly 1 empty slot in the array, and then we can issue a warning "Stack getting full!".
Now how to maintain this invariant? For every element of the 2nd stack, we just need to maintain a variable which says whether the last element was added to the left or to the right. Also, while doing any push() or pop() operations on the 1st or 3rd stack, we need to push2(pop2()) i.e. pop an element of the 2nd stack and push it on the 2nd stack again (to 'refresh' the invariant).
I'm not completely sure if this works ;) but its O(N) extra space and O(1) for all push/pop operations.
The approach was wrong, sorry.
- anujkaliaiitd July 16, 2012