Shivam Maharshi
BAN USERTotal Algorithms Geek
Ohh....but it is making this code looks complex.But then again you are returning the same array. Its gud.
- Shivam Maharshi August 21, 2012Dude...in which company was this asked ?
- Shivam Maharshi August 21, 2012Dude ignore that, May be some one didn't got that approach. But anyways I see that you're doing this in order O(n^2). This can be done in O(n) order, may be that's why some one didn't like it.
- Shivam Maharshi August 21, 2012Ohh....Well great then..!!
- Shivam Maharshi August 21, 2012Ohh...I'm sorry..my bad. I got the question correctly, Just din't read your input format properly. I got it now you are giving everyone at least 1 candy. But it seem a lil bit less obvious giving unequal amount of candies to the same performance kids even when they are seated consecutively.
- Shivam Maharshi August 21, 20121 - 1
2 - 2
3 - 1
@nitingupta180...did u mean this... ?
@nitingupta180.....the question also says that each kid must recieve at least one candy. So the answer has to be 5.You can't give one 2 a single candy and other 2 null candy.
- Shivam Maharshi August 21, 2012You don't have to do 2 passes. In first pass place the negatives on the left, the positive on the right, and the remaining must be zeroes. As when you initialize an array the value gets initialised with zero so you don't even need to set anything now. Just 1 pass required.
- Shivam Maharshi August 21, 2012/*
* This has a runtime of O(n).
* Places all the negative no on the left side.
* All the positive no on the right side.
* And all the zeroes in the middle.
*/
public int[] arrangeArray(int[] arr) {
int[] res = new int[arr.length];
int left = 0;
int right = arr.length - 1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] < 0) {
res[left] = arr[i];
left++;
} else if (arr[i] > 0) {
res[right] = arr[i];
right--;
}
}
return res;
}
You don't have to do 2 passes. In first pass place the negatives on the left, the positive on the right, and the remaining must be zeroes. As when you initialize an array the value gets initialised with zero so you don't even need to set anything now. Just 1 pass required.
- Shivam Maharshi August 21, 2012The runtime of this program would be denoted in the Big O Notation as O(n^2).
Explanation : Since N^2 is the factor which would contribute the most in the increase of the runtime as N increases, thus Log(n) can be ignored as it would not have any considerable increasing effect on the runtime compared to N^2, and the constant 4000 would not have any increasing effect on the runtime what so ever.
/* This just prints the upper triangle.
Similar logic can be applied to
print the lower triangle too */
public void getUpperTri(int n) {
int val = 0;
for(int i=1;i<=n;i++) {
val++;
for(int j=1;j<=i;j++) {
if(i%2==1) {
if(j!=1) {
val -= n-1;
}
} else {
if(j!=1) {
val += n-1;
}
}
System.out.println(val);
if(i%2==0 &&i==j) {
val += n-1;
}
}
}
}
/* This just prints the upper triangle.
Similar logic can be applied to
print the lower triangle too */
public void getUpperTri(int n) {
int val = 0;
for(int i=1;i<=n;i++) {
val++;
for(int j=1;j<=i;j++) {
if(i%2==1) {
if(j!=1) {
val -= n-1;
}
} else {
if(j!=1) {
val += n-1;
}
}
System.out.println(val);
if(i%2==0 &&i==j) {
val += n-1;
}
}
}
}
Just treat the left node of the given node as the root node. This will work fine.
- Shivam Maharshi August 21, 2012@Boobal.........Suppose you have coins of 2,3,4,5,6,7,2,3,1,4,3 Rs/-.
The question is that how can you make say 8Rs/- from them such that you have minimum no. of coins.
So the ans of this will be 2. ie.. 2 Rs/- Coin and 6Rs/- Coin, this make the total 8Rs/-.
Another combination could've been 2,2,3,1...but we did not choose this because this leads to total of 4 coins.
I hope this explains the problem to you.
It gives 2 as expected. But thanks anyways dude. :)
I just wrote this code and not with much thinking. I am really not sure of whether it will pass all the test cases.
Hi, this code runs with the order O(n^2). No DP involved. Can anyone please give me a test case in which it fails ?
- Shivam Maharshi August 17, 2012/*
* From a set of coins of some value. We find the minimum no. of coins
* required to get count. If not possible returns -1. Done in order O(n^2),
* way better than O(2^n) the brute force approach.
*/
public int getMinCoins(int[] coins, int count) {
int res = -1;
Arrays.sort(coins);
List<Integer> num = new ArrayList<Integer>();
List<Integer> temp = new ArrayList<Integer>();
List<Integer> rep = new ArrayList<Integer>();
for (int i = coins.length - 1; i > -1; i--) {
if (coins[i] == count) {
return 1;
} else if (coins[i] < count) {
for (int j = 0; j < num.size(); j++) {
if (coins[i] + num.get(j) == count) {
return rep.get(j) + 1;
} else if (coins[i] + num.get(j) < count) {
temp.add(coins[i] + num.get(j));
rep.add(rep.get(j) + 1);
// System.out.println("Num : "+(int)(coins[i] +
// num.get(j))+" Rep is : "+(int)(rep.get(j) + 1));
}
}
for (int j = 0; j < temp.size(); j++) {
num.add(temp.get(j));
}
temp.removeAll(temp);
num.add(coins[i]);
rep.add(1);
// System.out.println("Num : "+coins[i] +" Rep is : 1");
}
}
return res;
}
// This code has the order of O(n*m + (n-k)*(m-k)). But an extra array is needed.
public int maxMatSum(int[][] mat, int k) {
int res = 0;
int[][] num = new int[mat.length][mat[0].length];
int sum = 0;
for (int i = 0; i < mat.length; i++) {
sum += mat[i][0];
num[i][0] = sum;
}
sum = 0;
for (int j = 0; j < mat[0].length; j++) {
sum += mat[0][j];
num[0][j] = sum;
}
for (int m = 1; m < mat.length; m++) {
for (int n = 1; n < mat[0].length; n++) {
num[m][n] = mat[m][n] + num[m-1][n] + num[m][n-1] - num[m-1][n-1];
}
}
for (int m = 0; m < num.length - k; m++) {
for (int n = 0; n < num[0].length - k; n++) {
if(res < num[m+k][n+k] + num[m][n] - num[m+k][n] - num[m][n+k]) {
res = num[m+k][n+k] + num[m][n] - num[m+k][n] - num[m][n+k];
}
}
}
return res;
}
This will have Time Complexity of O(n). But this will have memory complexity of O(total). The time complexity is gud but the memory complexity is horrible. Thus I would recommend the solution with merge sorting first and then simple comparisons but the two consecutive range.
- Shivam Maharshi August 14, 2012public double getFraction(int[] start,int[] end, int total) {
double res = 0;
byte[] c= new byte[total+1];
for(int i=0;i<start.length;i++) {
for(int j=start[i];j<=end[i];j++) {
c[j] = 1;
}
}
for(int i=1;i<total+1;i++) {
if(c[i]==1) {
res++;
}
}
return res/total;
}
Infact 20. 1,4,7,8
- Shivam Maharshi August 14, 2012
but you don't need 2 passes. it can be done in just one pass.
- Shivam Maharshi August 21, 2012