saumya.tyagi6
BAN USER- 1of 3 votes
AnswersThere are N objects kept in a row. The ith object is at position x_i. You want to partition them into K groups. You want to move all objects belonging to the same group to the same position. Objects in two different groups may be placed at the same position. What is the minimum total amount by which you need to move the objects to accomplish this?
- saumya.tyagi6 in United States
Input:
The first line contains the number of test cases T. T test cases follow. The first line contains N and K. The next line contains N space seperated integers, denoting the original positions x_i of the objects.
Output:
Output T lines, containing the total minimum amount by which the objects should be moved.
Constraints:
1 <= T <= 1000
1 <= K <= N <= 200
0 <= x_i <= 1000
Sample Input:
3
3 3
1 1 3
3 2
1 2 4
4 2
1 2 5 7
Sample Output:
0
1
3
Explanation:
For the first case, there is no need to move any object.
For the second case, group objects 1 and 2 together by moving the first object to position 2.
For the third case, group objects 1 and 2 together by moving the first object to position 2 and group objects 3 and 4 together by moving object 3 to position 7. Thus the answer is 1 + 2 = 3.| Report Duplicate | Flag | PURGE
Facebook SDE-2 Algorithm
Complexity o(n)
- saumya.tyagi6 February 04, 20141. use divide and conquer like this
2. x is array of lower bounds and y is of upper bounds
3. and function is returning array of two elements
4.Divide array in two parts
5. calculate max interval from both side in bottom up manner.
6. If two intervals are overlapping return the lower bound of first one and upper bound of second one as result.
7. If they are not overlapping return the interval with most elements.
public static int [] maxInterval(int []x,int[] y,int start,int end)
{
if(start==end)
return new int []{x[start],y[start]};
int mid=(start+end)/2;
int a1[]=maxInterval(x, y, start, mid);
int a2[]=maxInterval(x, y, mid+1, end);
if(a1[0]<a2[0]&&a1[1]>=a2[0])
return new int[]{a1[0],a2[1]};
else if(a2[0]<a1[0]&&a2[1]>=a1[0])
return new int[]{a2[0],a1[1]};
else
{
if(a1[1]-a1[0]>a2[1]-a2[0])
return a1;
else return a2;
}
}
There Can be two approaches both are easy ones.
First.
1. Insert K elements in heap
2. after that delete min and add new element
3.repeat till the end
complexity nlogk
Second
This one also provides nlogk but needs a better implementation of merge sort
1.divide array in n/k parts
2. sort those subparts O(klogk) time
3.Merge them from left
void buildTreeFromList(int [][]a)
{
HashMap<Integer,ArrayList<Integer>> map=new HashMap<Integer,ArrayList<Integer>>();
int rootNode=a[0][0];
for(int i=0;i<a.length;i++)
{
if(map.containsKey(a[i][0]))
{
map.get(a[i][0]).add(a[i][1]);
}
else
{
map.put(a[i][0], new ArrayList<Integer>());
map.get(a[i][0]).add(a[i][1]);
}
if(rootNode==a[i][1])
rootNode=a[i][0];
}
preorder(temp(map,rootNode));
}
private Node temp(HashMap<Integer, ArrayList<Integer>> map, int rootNode) {
Node n=new Node();
n.info=rootNode;
if(map.containsKey(rootNode)==false)
return n;
ArrayList<Integer> list=map.get(rootNode);
n.left=temp(map,list.get(0));
if(list.size()>1)
n.right=temp(map,list.get(1));
return n;
}
1. Map all the elements as parent as key and children in a list
2.Meanwhile keep track of root node as well
3.After that use recursion and create Node for every entry in list.
4. Add zeroth element in left and second one on right side.
Correct me if I m wrong
1.We can traverse tree in inorder manner.
2. We will have two pointers prev and current.
3.When prev is equal to the node given current pointer will b our answer.
Correct me If I m wrong.
@Nuruddin-
See I m thinking of this problem as the largest node will have zero in updated tree since there is no larger node thn it. SO I m updating it with zero thats why I performed subtraction.
If u want that largest node will contain the vlue of its own in updated tree is well then no need of subtraction.
Let me know if u have any more issues
Not a o(n) solution see in recursion for traversing each node we will have linear time.
For each Node u r looping through the list which will also have o(h) time if h is the height of tree and internally String.valueOf() method will also run with linear time.
So ur code will work in linear time if height is smaller . But for larger trees it is certainly not linear.
1. Suppose if u persist preorder only postorder than how would u identify that which element will come to the left or which element will come to the right.
2. this will lead us to the different BST from the one which we persisted.
3.So by using only one traversal we will get differnet BSTs with same elements.
@kkr.ashish U checked x==0 which means there is no leaf node to that particular node that means it is a leaf node itself and i m also checking the same so it is the two different ways of doing same thing
- saumya.tyagi6 January 22, 2014@suzker-U r logic is right but the code u have provided will not print anything for any input
- saumya.tyagi6 January 22, 2014o(n) time complexity
- saumya.tyagi6 January 22, 2014We have to use Bottom up approach
1. Traverse the tree in postorder manner.
2.While traversing keep count of the leaf nodes
3. add nodes who have k leaves to list
4. At the end LIst will contain the ans
int getNodeWithKLeaves(Node root,int k,LinkedList<Integer> list)
{
if(root==null)
return 0;
int x=0;
x+=getNodeWithKLeaves(root.left, k, list);
x+=getNodeWithKLeaves(root.right, k, list);
if(root.left==null&&root.right==null)
x++;
if(k==x)
list.add(root.info);
return x;
}
Node makeTree(int a[],int start,int end)
{
if(start>end)
return null;
//to keep overflow away
int mid=start+(end-start)/2;
Node n=new Node();
n.info=a[mid];
n.left=makeTree(a,start,mid-1);
n.right=makeTree(a,mid+1,end);
return n;
}
.
1. Recursively calculate mid
2. Make it root node.
3. Nd keep doing this process for other two halves of array
T(n)=2T(n/2)+1
it will give us o(n) time complexity
space complexity-o(n) for recursive stack
@ricky we dont need to persist two traversals we can do it by only one
- saumya.tyagi6 January 22, 2014let me know if u have any problem
- saumya.tyagi6 January 21, 20141.see I m traversing right subtree first so we will get traversal in decreasing order.
2.And counter sum will held the sum of traverse elements
like if 5,3,2 is traversed thn sum will have 10.
3. for the current node we will change its value with the sum.
4. and current elements value before updation we will add in sum also bcz we need it further.
For both only the implementation will change complexity will remain same
so it doesnt matter
***serialization***
1. traverse tree using level order traversal
2. If a node dont have left or right child while serializing in its place serialize $(or any other sentinel value)
***deserialization***
1.read values from file (It is in level order)
2. if value is not sentinel thn it is a node add it to tree
3. make it child of its parent if current loop count is odd it is left child else it is right child
4. if it is a sentinel value set null in the left or right(whichever it is) pointer of parent
complexity o(n) for both operations
1. apply reverse inorder
2. keep track of sum of nodes while traversing
3. change the value of roots while traversing
public void sumofallgreater(Node root)
{
if(root==null)
return;
sumofallgreater(root.right);
sum+=root.info;
root.info=sum-root.info;
sumofallgreater(root.left);
}
-->sum is a static variable
- saumya.tyagi6 January 21, 2014in if condition there is x&1 sorry for typos.
- saumya.tyagi6 January 20, 2014Here is simple code in java. Steps are as following
1. Divisibility can be checked by checking whether last digit is 0 or 5.
2. Since complexity should be o(logn) .
3. If number is odd we can add 5 in it.
5. After that we have to check whether last digit is 0 or not.
6. Now u we can multiply it with 0.1 and after that we can cast it again in int.
7.Then multiply with ten.
8.After all these processes we should get the old number back;
9.If we dont get it number is not divisible.
static boolean check(int x) {
if((x&1)==1)
x+=5;
float y=((int)(x*0.1))*10;
if(y==x)
return true;
else return false;
}
1.Build the tree recursively.
- saumya.tyagi6 February 24, 20142.go through all the ancestors .
3.And make the connections while the stack is getting empty.