Sabbir Manandhar
BAN USER/**
* Java Solution
* O(n) time complexity and O(1) space complexity
*/
public static void process(String input, int width) {
int currentRow = 0;
int currentCol = -1;
for (int i = 0; i < input.length(); i++) {
int next = input.charAt(i) - 'A'; //next character
/** convert next character in to 2D location (row and col) based on input width of keyboard */
int row = next / width;
int col = next % width;
/** move robot hand from currentRow, currentCol to row, col */
if (row < currentRow) {
System.out.print("U" + (currentRow - row) + ", ");
} else if (row > currentRow){
System.out.print("D" + (row - currentRow) + ", ");
}
if (col < currentCol) {
System.out.print("L" + (currentCol - col) + ", ");
} else if (col > currentCol){
System.out.print("R" + (col - currentCol) + ", ");
}
if (i < input.length() - 1) {
System.out.print("T, ");
} else {
System.out.print('T');
}
/** change currentRow and currentCol to new location */
currentRow = row;
currentCol = col;
}
}
This solution has the O(n) time
public boolean isAP(int[] a) {
int max = Integer.NEGATIVE_INFINITY, min = POSITIVE_INIFINITY;
// determine max and min
// O(n)
for (int i = 0; i < a.length; i++) {
if (max < a[i]) max = a[i];
if (min > a[i]) min = a[i];
}
int diff = (max - min)/(a.length - 1);
boolean[] aa = new int[a.length];
for (int i = 0; i < a.length; i++) {
aa[i] = false;
}
for (int i = 0; i < a.length; i++) {
int index = (a[i] - min)/diff;
if (aa[index]) {
return false;
} else {
aa[index] = true;
}
}
return true;
}
I don't think we can rely on sum of arithmetic series. How about this series
2 4 4 10 10 ==> this satisfies the sum constraint but is not AP
you have used ArrayList, but the question asks to use LinkedList
- Sabbir Manandhar February 26, 2018