thelineofcode
BAN USERYou can also use a recursion to count all possibilities:
public static void main(String[] args) {
System.out.println(createString(0, 0, new StringBuilder(), 5));
}
public static int createString(int aCount, int bCount, StringBuilder sb, int n) {
if (sb.length() == n) {
System.out.println(sb);
return 1;
}
int aResult = 0;
int bResult = 0;
int cResult = 0;
if (aCount < 2) {
sb.append('a');
aResult = createString(aCount + 1, bCount, sb, n);
sb.setLength(sb.length() - 1);
}
if (bCount == 0) {
sb.append('b');
bResult = createString(0, bCount + 1, sb, n);
sb.setLength(sb.length() - 1);
}
sb.append('c');
cResult = createString(0, bCount, sb, n);
sb.setLength(sb.length() - 1);
return aResult + bResult + cResult;
}
Good sol. I made small modification of the code which clearly shows that it has O(n) time complexity.
public static void main(String[] args) {
Integer[] arr = { 1, 9, 8, 6, 3, 4, 8, 2, 10 };
Integer[] output = new Integer[arr.length];
Stack<Integer> stack = new Stack<Integer>();
int i = 0;
while (i < arr.length) {
if (stack.isEmpty() || arr[i] > arr[stack.peek()]) {
stack.push(i);
i++;
} else {
output[stack.pop()] = stack.isEmpty() ? null : arr[stack.peek()];
}
}
while (!stack.isEmpty()) {
output[stack.pop()] = stack.isEmpty() ? null : arr[stack.peek()];
}
System.out.println(Arrays.toString(output));
}
public static void main(String[] args) {
char[] chars = { 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'c', 'd', 'd', 'd', 'e', 'e' };
// char[] chars = { 'a', 'b', 'c' };
int count = 1;
char currentChar = chars[0];
int tail = 1;
for (int i = 1; i < chars.length; i++) {
if (chars[i] == currentChar) {
count++;
continue;
}
if (count > 1) {
chars[tail++] = (char) (count + '0');
}
chars[tail++] = chars[i];
currentChar = chars[i];
count = 1;
}
if (count > 1) {
chars[tail++] = (char) (count + '0');
}
Arrays.fill(chars, tail, chars.length, ' ');
System.out.println(Arrays.toString(chars));
}
Then you would have to check all combinations of triplets and it can not be done in O(n) time. But in this case, question states that the array contains only positive numbers and my solution is correct.
- thelineofcode July 10, 2013Actually the solution is quite simple - just keep tack of values which are less then 2:
public static boolean findTriplet(double[] arr) {
double first = Float.MAX_VALUE;
double sec = Float.MAX_VALUE;
double third = Float.MAX_VALUE;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 2) {
continue;
}
if (arr[i] <= first) {
third = sec;
sec = first;
first = arr[i];
} else if (arr[i] <= sec) {
third = sec;
sec = arr[i];
} else if (arr[i] <= third) {
third = arr[i];
}
double res = first + sec + third;
if (res > 1 && res < 2) {
System.out.println("Found triplet: " + first + " + " + sec + " + " + third + " = " + res);
return true;
}
}
System.out.println("Triplet was not found");
return false;
}
- thelineofcode July 15, 2013