aviundefined
BAN USERInstead of
if (!visited[i][j])
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}
Use this, it's more optimal
if (!visited[i][j] && a[i][j] == word.charAt(0))
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}
1) Count word by using DFS from each cell
2) Java implementation of above approach
public static int countWord(char[][] a, String word)
{
int wordLength = word.length();
char[] current = new char[wordLength];
int row = a.length;
int col = a[0].length;
boolean[][] visited = new boolean[row][col];
int count = 0;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (!visited[i][j])
{
count += countWord(a, i, j, current, 0, visited, word, row, col);
}
}
}
return count;
}
private static int countWord(char[][] a, int i, int j, char[] current, int index, boolean[][] visited, String word,
int row, int col)
{
int count = 0;
if (isSafe(a, visited, i, j, row, col, index, word))
{
current[index] = a[i][j];
if (current[index] != word.charAt(index))
{
return 0;
}
if (index == word.length() - 1)
{
return 1;
}
visited[i][j] = true;
index++;
count += countWord(a, i + 1, j, current, index, visited, word, row, col);
count += countWord(a, i - 1, j, current, index, visited, word, row, col);
count += countWord(a, i, j + 1, current, index, visited, word, row, col);
count += countWord(a, i, j - 1, current, index, visited, word, row, col);
visited[i][j] = false;
}
return count;
}
private static boolean isSafe(char[][] a, boolean[][] visited, int i, int j, int row, int col, int index, String word)
{
if ((i >= 0 && i < row) && (j >= 0 && j < col) && (!visited[i][j]) && (index < word.length()))
{
return true;
}
return false;
}
Java Implementation:
public static void findLongestStringWithTwoUniqueCharacters(char[] c)
{
char c1 = c[0], c2 = '1';
int sp1 = 0, ep1 = 0;
int sp2 = -1, ep2 = -1;
int len = 0;
int maxLen = -1;
int fep1 = 0, fep2 = 0, fsp1 = 0, fsp2 = 0;
char fc1 = 0, fc2 = 0;
for (int i = 0; i < c.length; i++)
{
if (c[i] == c1 && c2 == '1')
{
ep1 = i;
len++;
}
else if (c[i] != c1 && c2 == '1')
{
c2 = c[i];
sp2 = ep2 = i;
len++;
}
else if (c[i] == c2)
{
ep2 = i;
len++;
}
else if (c[i] == c1)
{
len++;
char tempC = c1;
c1 = c2;
c2 = tempC;
int temp = sp1;
sp1 = sp2;
sp2 = temp;
temp = ep1;
ep1 = ep2;
ep2 = temp;
ep2 = i;
}
else if (c[i] != c1 && c[i] != c2)
{
if (maxLen < len)
{
maxLen = len;
fep1 = ep1;
fsp1 = sp1;
fsp2 = sp2;
fep2 = ep2;
fc1 = c1;
fc2 = c2;
}
char tempC = c1;
c1 = c2;
c2 = tempC;
int temp = sp1;
sp1 = sp2;
sp2 = temp;
temp = ep1;
ep1 = ep2;
ep2 = temp;
c2 = c[i];
sp2 = ep2 = i;
int j = ep1;
len = 1;
while (c[j] == c1)
{
sp1=j;
len++;
j--;
}
}
}
// System.out.println("MaxLen: " + maxLen);
// System.out.println("char 1:" + fc1 + " From and to: " + fep1 + "," + fsp1);
// System.out.println("char 2:" + fc2 + " From and to: " + fep2 + "," + fsp2);
prinSolution(c, fsp1, fsp2, fep1, fep2, maxLen);
}
private static void prinSolution(char[] c, int fsp1, int fsp2, int fep1, int fep2, int maxLen)
{
int start = fsp1 > fsp2 ? fsp2 : fsp1;
int end = fep1 > fep2 ? fep1 : fep2;
System.out.println("Input : " + String.valueOf(c));
System.out.print("Output: ");
for (int i = start; i <= end; i++)
{
System.out.print(c[i]);
}
System.out.println();
System.out.println("MaxLen: " + maxLen);
System.out.println("-----------------------------------------");
}
Simple java implementation
public static char[] removeBandAC(char[] chars)
{
int i = 0, r = 0, n = chars.length;
while (i < n)
{
if (chars[i] == 'b')
{
// do nothing
}
else if (chars[i] == 'a' && i < n - 1 && chars[i + 1] == 'c')
{
i++;
}
else
{
chars[r] = chars[i];
r++;
}
i++;
}
while (r < n)
{
chars[r] = '\0';
r++;
}
return chars;
}
Forgot to add code:
public static void findPairSorted(Triplet[] triplets)
{
Stack<Pair> s = new Stack<>();
List<Pair> result = new ArrayList<>();
result.add(new Pair(triplets[0].c, triplets[0].first));
Pair p = new Pair(triplets[0].c, triplets[0].second);
s.push(p);
int i = 1;
while (!s.isEmpty() && i < triplets.length)
{
Pair first = new Pair(triplets[i].c, triplets[i].first);
Pair second = new Pair(triplets[i].c, triplets[i].second);
while (!s.isEmpty() && s.peek().data <= first.data)
{
result.add(s.pop());
}
s.push(first);
while (!s.isEmpty() && s.peek().data <= second.data)
{
result.add(s.pop());
}
s.push(second);
i++;
}
while (!s.isEmpty())
{
result.add(s.pop());
}
System.out.println(result);
}
1) For every truplet we will have two pair. Lets call them first and second.
Example: (a,1,5) --> first = (a,1) and second = (a,5)
2) Create one stack
2) push first entry add first pair in output and push second pair in stack
4) Then for every truplet, do the following steps for first and second pair
4.1) if s.peek().data less than equal to pair then pop from stack and add in output
Java implementation of following algo:
Actually question is not clear much that if that leaf is eaten already then any Caterpillar can jump on that position or not.
If Caterpillar can jump on eaten leaf then we can remove leafs[pos] == 0 from while loop.
If Caterpillar can not jump on eaten leafs then this condition is required.
public static int numberOfUneatenLeafs(int[] caterpiler, int n) throws Exception
{
if (caterpiler == null || caterpiler.length == 0 || n <= 0)
{
throw new Exception();
}
Util.printArray("Caterpiler jumps:", caterpiler);
System.out.println("Numbers of leafs: " + n);
int count = n;
int[] leafs = new int[n + 1];
int K = caterpiler.length;
for (int k = 0; k < K && count > 0; k++)
{
int pos = 0;
pos += caterpiler[k];
while (pos <= n && leafs[pos] == 0 && count > 0)
{
leafs[pos] = 1;
pos += caterpiler[k];
count--;
}
}
printUneatenLeafs(leafs);
System.out.println("Number of uneaten leafs: " + count);
System.out.println("-------------------------------------------");
return count;
}
private static void printUneatenLeafs(int[] leafs)
{
int n = leafs.length;
System.out.print("Uneaten leafs: ");
for (int i = 1; i < n; i++)
{
if (leafs[i] == 0)
{
System.out.print(i + ",");
}
}
System.out.println();
}
public static void divide(int a, int b)
{
int quotient = a / b;
int rem = a % b;
int[] hash = new int[b];
for (int i = 0; i < b; i++)
{
hash[i] = -1;
}
int i = 0;
StringBuilder decimals = new StringBuilder();
boolean isRepeating = true;
while (rem != 0 && hash[rem] == -1)
{
hash[rem] = i;
i++;
rem *= 10;
decimals.append(rem / b);
rem = rem % b;
if (rem == 0)
{
isRepeating = false;
break;
}
}
String output = String.valueOf(quotient)+".";
if (isRepeating)
{
int repIndex = hash[rem];
String decimalStr = decimals.toString();
output = output + decimalStr.substring(0, repIndex) + "(" + decimalStr.substring(repIndex) + ")";
}
else
{
output = output + decimals.toString() + "(0)";
}
System.out.println(a + "/" + b + " = " + output);
System.out.println("--------------------------------------------");
}
Check this link:
geeksforgeeks.org/rearrange-array-alternating-positive-negative-items-o1-extra-space/
Isn't similar to changing root value to all the nodes which are before (including that node) in in-order traversal.
Algo:
1) first visit left node
2) then sum = sum + root-->data
3) root-->datra = sum
4) Visit right node
void changeData(Node root, int sum)
{
changeData(root.left,sum);
sum = sum + root.data;
root.data = sum + root.data;
changeData(root.right,sum);
}
Please see this link.
thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/
Algo:
1)Assumption is a will contain the numbers less than length of array. So we can first do minus one from each element for ease of writing the algo.
2) change a[a[i]%n] = x[i]*n + a[a[i]%n]
3) Then x[i] = a[i]/n
4) Restore a, by a[i] = a[i]%n;
code:
public static void converArray(int[] x, int[] a)
{
int n = x.length;
for (int i = 0; i < n; i++)
{
System.out.println("i: "+(a[i] % n));
a[a[i] % n] = x[i]*n + a[a[i] % n];
}
for (int i = 0; i < n; i++)
{
x[i] = a[i] / n;
}
}
1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map
Code:
public static void findEvenOccurringNumbers(int[] a)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
for (int num : a)
{
if (hash.containsKey(num))
{
hash.put(num, hash.get(num) ^ 1);
}
else
{
hash.put(num, 1);
}
}
for (Entry<Integer, Integer> entry : hash.entrySet())
{
if (entry.getValue() == 0)
{
System.out.println(entry.getKey());
}
}
}
1) Create a HashMap
2) Iterate over the array
3) If HashMap contains the entry the take put the value^1
4) Else put 1 for that entry
5) In the end numbers which are present even number of times will have value 0 in hash map
Code:
public static void findEvenOccurringNumbers(int[] a)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
for (int num : a)
{
if (hash.containsKey(num))
{
hash.put(num, hash.get(num) ^ 1);
}
else
{
hash.put(num, 1);
}
}
for (Entry<Integer, Integer> entry : hash.entrySet())
{
if (entry.getValue() == 0)
{
System.out.println(entry.getKey());
}
}
}
Java Implementation of this problem. Time complexit o(m*n)
public static boolean isAnagramExists(String src, String target)
{
if (src == null || "".equals(src.trim()) || target == null)
{
return false;
}
Map<String, Integer> targetCount = new HashMap<String, Integer>();
Map<String, Integer> srcCount = new HashMap<String, Integer>();
int targetLen = target.length();
int srcLen = src.length();
for (int i = 0; i < target.length(); i++)
{
increaseCharCount(target, targetCount, i);
increaseCharCount(src, srcCount, i);
}
int start = 0;
while (start < srcLen)
{
int j = 0;
for (j = 0; j < targetLen; ++j)
{
String targetLetter = String.valueOf(target.charAt(j));
if (targetCount.get(targetLetter) != srcCount.get(targetLetter))
{
break;
}
}
if (j == targetLen)
{
return true;
}
if (start + 1 + targetLen > srcLen)
break;
decreaseCharCount(src, srcCount, start);
increaseCharCount(src, srcCount, start + targetLen);
start++;
}
return false;
}
private static void decreaseCharCount(String string, Map<String, Integer> map, int i)
{
String targetLetter = String.valueOf(string.charAt(i));
if (map.get(targetLetter) == null)
{
map.put(targetLetter, 0);
}
else
{
int count = map.get(targetLetter);
map.put(targetLetter, --count);
}
}
private static void increaseCharCount(String string, Map<String, Integer> map, int i)
{
String targetLetter = String.valueOf(string.charAt(i));
if (map.get(targetLetter) == null)
{
map.put(targetLetter, 1);
}
else
{
int count = map.get(targetLetter);
map.put(targetLetter, ++count);
}
}
Steps
1) Create Adjacency List for nodes.
As in given example graph is undirected so adj list will look like this
0 -> 1,2
1->0,2
2-->0,1
4-->1
2) Pick one edge and get adj list for both nodes.
3) Count number of common elements in adj list
4) Repeat step 2 and 3 for all the edges
Number of triangles= (Number of common elements)/6 as it's undirected graph for directed graph it will be divided by 3
Sum approach will fail for this case..so only by checking sum is not sufficient
555 555 555
555 555 555
555 555 555
Simple DFS Kind of solution for this
Node
{
Node next;
Node nested;
int value;
}
void iterator(Node head)
{
if(head == null)
return;
System.out.println(head->value);
iterator(node->nested);
iterator(node->next);
Simple DFS Kind of solution for this
Node
{
Node next;
Node nested;
int value;
}
void iterator(Node head)
{
if(head == null)
return;
System.out.println(head->value);
iterator(node->nested);
iterator(node->next);
Simple DFS Kind of solution for this
Node
{
Node next;
Node nested;
int value;
}
void iterator(Node head)
{
if(head == null)
return;
System.out.println(head->value);
iterator(node->nested);
iterator(node->next);
Simple DFS Kind of solution for this
Node
{
Node next;
Node nested;
int value;
}
void iterator(Node head)
{
if(head == null)
return;
System.out.println(head->value);
iterator(node->nested);
iterator(node->next);
Simple DFS Kind of solution for this
Node
{
Node next;
Node nested;
int value;
}
void iterator(Node head)
{
if(head == null)
return;
System.out.println(head-->value);
iterator(node.nested);
iterator(node.next);
We can consider this Binary Tree where next pointer of Linked List Node is equivalent to right node of Binary Tree and Nested pointer of Linked List Node as left node of Binary tree. Then simple do pre-order traversal.
- aviundefined January 16, 2014Build a Prefix tree and while building a tree also ignore the prefixes which are greater than the target. Like in this example {5,2,1,4,3,6,7,8} all those prefix which are greater than 333 will be ignored. 521, 5214, 52143, 521436, 5214367, 52143678 will be ignored . Only valid prefixes are 52 and 5. Similarly for for selecting prefix for child elements ignored alll the prefixes which are greater than the target. Then on that tree Perform DFS (Pre order) and check for sum on each setup.
.
@HadoopUser
I agree to your points but my point is I am not dependent on hashMap insertion order to check the duplicates. Order will be maintained by array iteration order.
Create one hash map and start putting array elements one by one. Before putting elements in hash map just check whether it's already present in hash map or not. If already present in hash map then it's duplicate and print it.
Time Complexity = O(n)
Space Complexity = O(n)
Declare a product array of lenght n such that
product[i] = Max( product[i-1]*a[i] , a[i])
Max(product) is the answer
Declare a product array of lenght n such that
product[i] = Max( product[i-1]*a[i] , a[i])
Max(product) is the answer
Correct solution is
1) root.data >= root-->left.data and root.data >= Max(root-->left) and root--left is BST
2) root.data <= root-->right.data and root.data <= Min(root-->right) and root-->right is BST
public boolean isBST(BinaryNode node)
{
boolean isBst = true;
if (node == null)
{
return true;
}
if(node.left != null)
{
isBst = (node.data >= node.left.data) && (node.data >= max(node.left).data) && (isBST(node.left));
}
if(isBst && node.right != null)
{
isBst = (node.data <= node.right.data) && (node.data <= min(node.right).data) && (isBST(node.right));
}
return isBst;
}
public BinaryNode min(BinaryNode node)
{
if(node == null)
{
return node;
}
if (node.left == null)
{
return node;
}
else
{
return min(node.left);
}
}
public BinaryNode max(BinaryNode node)
{
if (node.right == null)
{
return node;
}
else
{
return max(node.right);
}
}
There is mistake in the solution. If root node is greater than or equal to left node and smaller than or equal to right node and both left node and right node it self is BST then also it is possible that it's not a valid bst. You need to add a condition and need to check it recursively that root node is always greater than or equal to Max(root-->left) and less than or equal to Min(root-->right)
here is the java implementation of this
public boolean isBST(BinaryNode node)
{
boolean isBst = true;
if (node == null)
{
return true;
}
if(node.left != null)
{
isBst = (node.data >= node.left.data) && (node.data >= max(node.left).data) && (isBST(node.left));
}
if(isBst && node.right != null)
{
isBst = (node.data <= node.right.data) && (node.data <= min(node.right).data) && (isBST(node.right));
}
return isBst;
}
Another possible solution is
1) First find the maximum Sum
2) Then print the path which has sum = maximum sum found in first step
public void findSumPath(BinaryNode node, int currentSum, String path, int sum)
{
if (node != null)
{
currentSum = currentSum + node.data;
path = path + node.data + "-->";
if (currentSum == sum)
{
System.out.println(path);
return;
}
else if (currentSum < sum)
{
findSumPath(node.left, currentSum, path, sum);
findSumPath(node.right, currentSum, path, sum);
}
else
{
System.out.println("No such path exists");
return;
}
}
}
public int findMaxSum(BinaryNode node)
{
if (node == null)
{
return 0;
}
return (node.data + max(findMaxSum(node.left), findMaxSum(node.right)));
}
public int printMaxSum(BinaryNode node)
{
int maxSum = findMaxSum(node);
findSumPath(node, 0, "", maxSum);
System.out.println();
return maxSum;
}
private int max(int value1, int value2)
{
if (value1 >= value2)
{
return value1;
}
return value2;
}
We can break the problem in two steps
1) Get the leaf node for which sum is maximum
2) Once we have target leaf node, print the path from root to traget
public boolean printPath(BinaryNode node, BinaryNode target)
{
if(node == null)
{
return false;
}
if(node.equals(target) || printPath(node.left, target) || printPath(node.right, target))
{
System.out.print(node.data + "-->");
return true;
}
return false;
}
private int maxSum = 0;
private BinaryNode maxSumLeaf = null;
private void getMaxSumVodeLeaf(BinaryNode node, int currentSum)
{
if(node == null)
{
return;
}
currentSum = currentSum + node.data;
if(node.left == null && node.right == null)
{
if(currentSum >= maxSum)
{
maxSum = currentSum;
maxSumLeaf = node;
}
}
getMaxSumVodeLeaf(node.left, currentSum);
getMaxSumVodeLeaf(node.right, currentSum);
}
public int getMaxSum(BinaryNode node)
{
if(node == null)
{
return 0;
}
maxSum = 0;
maxSumLeaf = null;
getMaxSumVodeLeaf(node, 0);
return maxSum;
}
public int printMaxSumPath(BinaryNode node)
{
getMaxSum(node);
printPath(node, maxSumLeaf);
System.out.println();
return maxSum;
}
private static int getSubStringCount(char[] parent, char[] child)
{
int j = 0;
int count = 0;
int i = 0;
while(i < parent.length)
{
if(parent[i] == child[j])
{
if(j == child.length - 1)
{
count++;
j = 0;
i++;
}
else
{
j++;
i++;
}
}
else
{
i++;
}
}
return count;
}
f(n) = a^n that can be written as
assume h(n) = GreatestIntegerFuntion(n)
then
a^n = a^h(n/2) * a^(n - h(n/2))
package com.problems;
public class PowerRecuresion
{
public static void main(String[] args)
{
testPower();
}
public static void testPower()
{
double a = -3;
int n = 6;
System.out.println("Power of " + a + " to the power " + n + " = " + power(a, n));
}
/**
* Time complexity of this is log(n) n = power;
*
* @param a
* - number
* @param n
* - power
* @return return a^n;
*/
public static double power(double a, int n)
{
if (n < 0)
{
return 0;
}
if (n == 0)
{
return 1;
}
else if (n == 1)
{
return a;
}
else
{
return power(a, n / 2) * power(a, n - n / 2);
}
}
}
package com.problems;
import java.util.ArrayList;
import java.util.List;
public class FindCommonElements
{
public static void main(String[] args)
{
testFindCommon();
}
public static void testFindCommon()
{
int[] a = {1,2,4,8,9,10,13,14,16};
int[] b = {5,7,8,12,14,15};
System.out.println(findCommonElements(a, b));
}
public static List<Integer> findCommonElements(int[] a, int[] b)
{
List<Integer> commonElements = new ArrayList<Integer>();
int i = 0, j = 0;
int sizeOfA = a.length;
int sizeOfB = b.length;
while(i < sizeOfA && j < sizeOfB)
{
if(a[i] < b[j])
{
i++;
}
else if(a[i] > b[j])
{
j++;
}
else
{
commonElements.add(a[i]);
i++;
j++;
}
}
return commonElements;
}
}
This is a modification of binary search, so time complexity is o(logn).
package com.problems;
public class FindElementInRotatedSorted
{
public static void main(String[] args)
{
test();
}
private static void test()
{
int[] a = { 5, 6, 7, 8, 9, 1, 2, 3 };
int key = 2;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));
key = 9;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));
key = 6;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));
key = 10;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));
key = 4;
System.out.println(key + ": " + findElementInRotatedSorted(a, 0, a.length - 1, key));
}
public static int findElementInRotatedSorted(int[] a, int start, int end, int key)
{
if (end < start)
{
return -1;
}
int middle = (start + end) / 2;
if (a[middle] == key)
{
return middle;
}
if (a[start] <= a[middle])
{
if (key < a[middle] && key >= a[start])
{
return findElementInRotatedSorted(a, start, middle - 1, key);
}
else
{
return findElementInRotatedSorted(a, middle + 1, end, key);
}
}
else
{
if (a[middle] < key && key <= a[end])
{
return findElementInRotatedSorted(a, middle + 1, end, key);
}
else
{
return findElementInRotatedSorted(a, start, middle - 1, key);
}
}
}
}
It's Moore's Voting Algorithm
1) Find the candidate who can possibly present more than n/2 in array. Remember it's a candidate element, it's not a element who has maximum frequency in the index
2) Then check that obtained candidate is majority element i.e. it occurs more than n/2 times
package com.problems;
public class MooresVotingAlgorithm
{
public static void main(String[] args)
{
testMooreVotingAlgo();
}
public static void testMooreVotingAlgo()
{
int[] a = { 4, 4, 4, 5, 6, 7, 10, 8, 10 };
System.out.println("Length: " + a.length);
int candidate = findCandidate(a);
System.out.println("Candidate: " + candidate);
boolean isMajority = isMajority(a, candidate);
if (isMajority)
{
System.out.println("Majority element: " + candidate);
}
else
{
System.out.println("Majority element not found");
}
}
public static int findCandidate(int[] a)
{
int size = a.length;
int candidateIndex = 0;
int count = 1;
for (int i = 1; i < size; i++)
{
if (a[candidateIndex] == a[i])
{
count++;
}
else
{
count--;
}
if (count == 0)
{
candidateIndex = i;
count = 1;
}
}
return a[candidateIndex];
}
public static boolean isMajority(int[] a, int candidate)
{
int size = a.length;
boolean isMajority = false;
int count = 0;
for (int i = 0; i < a.length; i++)
{
if (a[i] == candidate)
{
count++;
}
if (count > size / 2)
{
isMajority = true;
break;
}
}
return isMajority;
}
}
There are three types of problems possible with String reverse
1) Reverse the whole string:
Input: This is a test
Output: tset a si sihT
2) Reverse words in place
Input: This is a test
Output: sihT si a tset
3) Reverse only the words:
Input: This is a test
Output: test a is This
So for first problem just we need to divide this into smaller problem to reverse this string
Then second one can be done by just reversing the Sub strings in place
Then third one , just a combination of first and two. Reverse this string, then reverse the words in place.
package com.problems;
public class ReverseString
{
public static void main(String[] args)
{
String test = " This is a test ";
System.out.println("Orignal String: " + test);
char[] chars = reverseString(test.toCharArray(), 0, test.toCharArray().length - 1);
System.out.println(String.valueOf("Reverse string: " + String.valueOf(chars)));
chars = reverseStringWordsInPlace(test.toCharArray());
System.out.println(String.valueOf("Reverse words in place: " + String.valueOf(chars)));
chars = reverseStringWordsInPlace(chars);
System.out.println(String.valueOf("Reverse only words: " + String.valueOf(chars)));
}
public static char[] reverseStringWordsInPlace(char[] chars)
{
int start = 0, end = 0;
for (int i = 0; i < chars.length; i++)
{
if (" ".equals(String.valueOf(chars[i])))
{
reverseString(chars, start, i - 1);
start = i + 1;
}
}
reverseString(chars, start, chars.length - 1);
return chars;
}
public static char[] reverseString(char[] chars, int start, int end)
{
if (end < start)
{
return chars;
}
if (chars.length == 0 || chars.length == 1)
{
return chars;
}
swap(chars, start, end);
return reverseString(chars, ++start, --end);
}
public static char[] swap(char[] chars, int i, int j)
{
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return chars;
}
public static String reverseString(String s)
{
if (s == null || "".equals(s))
{
return "";
}
int length = s.length();
if (s.length() == 1)
{
return s;
}
return s.charAt(length - 1) + reverseString(s.substring(1, length - 1)) + s.charAt(0);
}
}
public class ReverseString
{
public static void main(String[] args)
{
String test = "This is a test";
System.out.println(test);
System.out.println(reverseString(test));
}
public static String reverseString(String s)
{
if (s == null || "".equals(s))
{
return "";
}
int length = s.length();
if (s.length() == 1)
{
return s;
}
return s.charAt(length - 1) + reverseString(s.substring(1, length - 1)) + s.charAt(0);
}
}
1) First find the index of the element by using binarySearch
2) If index find by binary Search is not equal to -1 i.e. element is found then
a) Recursively find the first occurrence of element in array[start, binarySearchIndex]
b) Recursively find the last occurrence of element in array[binarySearchIndex, end]
public static int firstOccurance(int[] a, int start, int end, int key)
{
if (start > end)
{
return -1;
}
if (start == end & key == a[start])
{
return start;
}
int middle = (start + end) / 2;
if (key == a[middle])
{
return firstOccurance(a, start, middle, key);
}
else
{
return firstOccurance(a, middle + 1, end, key);
}
}
public static int lastOccurance(int[] a, int start, int end, int key)
{
if (start > end)
{
return -1;
}
if (start == end & key == a[start])
{
return start;
}
int middle = (start + end) / 2 + 1;
if (key == a[middle])
{
return lastOccurance(a, middle, end, key);
}
else
{
return lastOccurance(a, start, middle - 1, key);
}
}
public static int binarySearch(int[] a, int start, int end, int key)
{
if (end < start)
{
return -1;
}
int middle = (start + end) / 2;
if (key == a[middle])
{
return middle;
}
else if (key > a[middle])
{
return binarySearch(a, middle + 1, end, key);
}
else
{
return binarySearch(a, start, middle - 1, key);
}
}
public static int[] findRangeBinarySearch(int[] a, int key)
{
int[] result = { -1, -1 };
int binIndex = binarySearch(a, 0, a.length, key);
if (binIndex != -1)
{
result[0] = firstOccurance(a, 0, binIndex, key);
result[1] = lastOccurance(a, binIndex, a.length - 1, key);
}
return result;
}
1)First Sort Array.
2) Then iterate the array,
a) if element is greater than the sum then continue
b) if element is equal to the sum then just print the element and continue
c) if both a & b if not true then ,
i) we need to iterate only for half of the array to avoid duplicates. Example (1,6) and (6,1).
ii) find the element in array by using binary search whose value is (sum - element at i), if it is found then print the pair
package com.problems;
public class FindCombinationOfSum
{
public static void main(String[] args)
{
findComibination();
}
public static void findComibination()
{
int[] a = { 2, 3, 1, 4, 5, 7, 6 };
int sum = 7;
a = mergeSort(a, 0, a.length - 1);
int search = -1;
int searchIndex = -1;
for (int i = 0; i < a.length; i++)
{
if (a[i] > sum)
{
continue;
}
if (a[i] == sum)
{
System.out.println(a[i]);
continue;
}
if (i < a.length / 2)
{
search = sum - a[i];
searchIndex = binarySearchIterative(a, search, 0, a.length - 1);
if (searchIndex != -1)
{
System.out.print(a[i] + "," + search);
System.out.println();
}
}
}
}
public static int[] mergeSort(int[] a, int p, int r)
{
if (p < r)
{
int q = (r + p) / 2;
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
merge(a, p, q, r);
}
return a;
}
private static int[] merge(int[] a, int p, int q, int r)
{
int n1 = q - p + 1;
int n2 = r - q;
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
for (int i = 0; i < n1; i++)
{
leftArray[i] = a[p + i];
}
for (int j = 0; j < n2; j++)
{
rightArray[j] = a[q + 1 + j];
}
int i = 0, j = 0, k = p;
while (i < n1 && j < n2 && k <= r)
{
if (leftArray[i] <= rightArray[j])
{
a[k++] = leftArray[i++];
}
else
{
a[k++] = rightArray[j++];
}
}
while (i < n1 && k <= r)
{
a[k++] = leftArray[i++];
}
while (j < n2 && k <= r)
{
a[k++] = rightArray[j++];
}
return a;
}
private static final int NOT_FOUND = -1;
public static int binarySearchIterative(int[] a, int value, int start, int end)
{
while(start <= end)
{
int middle = (start + end)/2;
if(value == a[middle])
{
return middle;
}
else if(value > a[middle])
{
start = middle + 1;
}
else
{
end = middle - 1;
}
}
return NOT_FOUND;
}
public static void printArray(String tag, int[] a)
{
System.out.print(tag + ": ");
for (int i = 0; i < a.length; i++)
{
System.out.print(a[i] + ",");
}
System.out.println("");
}
}
Implementation by modification of BFS
- aviundefined September 14, 2014