jerry
BAN USERWell, is the question not just about counting how many steps it takes to reach the 1 from the number given by following the sequence
public static int getlongestCollapsesequence(int n, int count){
System.out.print(n + " ");
if(n==1)
return count;
if(n%2 == 0)
return getlongestCollapsesequence(n/2, count++);
else
return getlongestCollapsesequence(3*n+1, count++);
}
- Sort the array first using quick sort
- then you can use the following logic
public static void sum(int []array,int sum){
int start = 0,end=array.length-1;
while(start<end){
if(array[start]+array[end]==sum)
{
System.out.println(array[start]+ ", "+array[end]);
start++;
end--;
}
else if(array[start]+array[end] > sum){
end--;
}
else if(array[start]+array[end] < sum){
start++;
}
}
}
public static void removeInterval(int []interval, int[]input){
ArrayList<Integer> result = new ArrayList<Integer>();
for(int i=0;i<interval.length;i=i+2){
if(interval[i] <input[0]){
result.add(interval[i]);
result.add(interval[i+1]);
}
else if(interval[i] >=input[1]){
result.add(interval[i]);
result.add(interval[i+1]);
}
}
System.out.println(result.toString());
}
- jerry July 13, 2013Algorithm for linear time is
1) consider a string for eg abaaba, we transform the string as #a#b#a#a#b#a#
2) Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends for eg till Ci. Then we can take Ci as the new center and try to expand
for # a # b # a # a # b # a#
P[] 0 1 0
which shows that at we have palindrome of length 1 taking a as center, now we again start taking b as center as the lest and right character's don't match around #
for # a # b # a # a # b # a #
P[] 0 1 0 3 0 1 6 1 0 3 0 1 0
which shows that at we have palindrome of length 3 taking b as center, now we again start taking # as center and the longest palindrome is at P6
Algorithm for linear time is
1) consider a string for eg abaaba, we transform the string as #a#b#a#a#b#a#
2) Manacher's algorithm fills in a table P[i] which contains how far the palindrome centered at i extends for eg till Ci. Then we can take Ci as the new center and try to expand
for # a # b # a # a # b # a#
P[] 0 1 0
which shows that at we have palindrome of length 1 taking a as center, now we again start taking b as center as the lest and right character's don't match around #
for # a # b # a # a # b # a #
P[] 0 1 0 3 0 1 6 1 0 3 0 1 0
which shows that at we have palindrome of length 3 taking b as center, now we again start taking # as center
So it shows that at P6 we have longest palindrome. of length 6
'abaaba'
public static void permutation(String s) {
permutation("", s);
}
private static void permutation(String prefix, String s) {
int n = s.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++) {
permutation(prefix + s.charAt(i),
s.substring(0, i) + s.substring(i + 1, n));
}
}
}
public static void listStructure(String path) {
listStructure(new File(path));
}
public static void listStructure(File file) {
if (file.isDirectory()) {
for (File f : file.listFiles()) {
if (f.isDirectory())
System.out.println(f.getAbsolutePath());
listStructure(f);
}
}
if (file.isFile()) {
System.out.println(file.getAbsolutePath());
}
}
public int LCA(int value1,int value2){
Node node1 = find(value1);
Node node2 = find(value2);
int depth1 = depth(value1);
int depth2 = depth(value2);
if(depth1>depth2)
{
while(depth1>depth2)
{
node1 = node1.getParent();
depth1--;
}
}else if(depth2>depth1)
{
while(depth2>depth1)
{
node2 = node2.getParent();
depth2--;
}
}
while(node1 != null|| node2!= null){
if( node1 == node2)
break;
node1 = node1.getParent();
node2 = node2.getParent();
}
return node1.getValue();
}
public NodeQueue bfs(Node traverseNode, int level) {
NodeQueue nodeQueue = new NodeQueue();
NodeQueue resultQueue = new NodeQueue();
traverseNode.setLevel(1);
nodeQueue.push(traverseNode);
resultQueue.push(traverseNode);
while (!nodeQueue.isEmpty()) {
traverseNode = nodeQueue.pop();
level = traverseNode.getLevel();
level++;
if (traverseNode.getLeft() != null) {
traverseNode.getLeft().setLevel(level);
nodeQueue.push(traverseNode.getLeft());
// resultQueue.push(traverseNode.getLeft());
}
if (traverseNode.getRight() != null) {
traverseNode.getRight().setLevel(level);
nodeQueue.push(traverseNode.getRight());
// resultQueue.push(traverseNode.getRight());
}
if(level%2==0){
if (traverseNode.getRight() != null) {
resultQueue.push(traverseNode.getRight());
}
if (traverseNode.getLeft() != null) {
resultQueue.push(traverseNode.getLeft());
}
}
else
{
if (traverseNode.getLeft() != null) {
resultQueue.push(traverseNode.getLeft());
}
if (traverseNode.getRight() != null) {
resultQueue.push(traverseNode.getRight());
}
}
}
return resultQueue;
}
public class Keypad {
public static final String[] keypad = {" ", " ", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
static StringBuffer s=new StringBuffer();
public void printAlphabets(int number){
int digit = number%10;
int i;
if(number == 0)
{
System.out.print(s.toString()+", ");
return;
}
String currentString = keypad[digit];
for(i = 0;i<currentString.length();i++){
s.append(currentString.charAt(i));
printAlphabets(number/10);
s.delete(s.length()-1,s.length());
}
}
public static void main(String argv[]) {
Keypad key = new Keypad();
key.printAlphabets(410292);
}
}
public int search_KMP(char[] text, char[] word) {
int m = 0, i = 0;
int[] t = table_KMP(text);
while (m + i < text.length) {
if (text[m + i] == word[i]) {
if (i == word.length-1) {
return m;
}
i = i + 1;
} else {
m = m + i - t[i];
if (t[i] > -1)
i = t[i];
else
i = 0;
}
}
return m;
}
public int[] table_KMP(char[] word) {
int t[] = new int[word.length];
t[0] = -1;
t[1] = 0;
int pos = 2, cnd = 0;
while (pos < word.length) {
if (word[pos - 1] == word[cnd]) {
cnd += 1;
t[pos] = cnd;
pos += 1;
} else if (cnd > 0) {
cnd = t[cnd];
} else {
t[pos] = 0;
pos += 1;
}
}
return t;
}
public int occurence(int k,String text, String word){
int i,index = 0,position = 0;
for(i = 0;i<k;i++){
text = text.substring(index);
index = search_KMP(text.toCharArray(),word.toCharArray());
if(i != k-1)
{
index = index +word.length();
}
position = position+index;
}
return position;
}
public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
|| (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue()- key);
Double diffNode = Math.abs(traverseNode.getValue()- key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}
public int findNearest(double key) {
Node previousNode = null;
Node traverseNode = root;
int absValue;
float value;
while (traverseNode != null) {
if (key < traverseNode.getValue()) {
previousNode = traverseNode;
traverseNode = traverseNode.getLeft();
} else {
previousNode = traverseNode;
traverseNode = traverseNode.getRight();
}
if ((traverseNode == null)
|| (key > previousNode.getValue() && key < traverseNode
.getValue())) {
break;
}
}
Double diffParent = Math.abs(previousNode.getValue()- key);
Double diffNode = Math.abs(traverseNode.getValue()- key);
if(diffParent <diffNode){
return previousNode.getValue();
}else
{
return traverseNode.getValue();
}
}
public void incrementNumber(int num[]) {
int[] result = new int[num.length];
int carry = 1;
for (int i = num.length - 1; i >= 0; i--) {
result[i] = num[i] + carry;
if (result[i] > 9) {
if (i == 0) {
result[i] = result[i] % 10;
result = incrementArray(result);
result[i] = 1;
} else {
result[i] = result[i] % 10;
carry = 1;
}
} else {
carry = 0;
}
}
for (int i = 0; i < result.length; i++) {
System.out.println(result[i] + " ");
}
}
public int[] incrementArray(int result[]) {
int[] newArray = new int[result.length + 1];
for (int i = result.length - 1; i >= 0; i--) {
newArray[i + 1] = result[i];
}
return newArray;
}
The filling of the cups with water need to be affected by the water left in the jug for the rest of cups .So after filling the water in cups at each level, we need to recalculate the water left in jug and the %of water to be filled in each cups as we go down
V =capacity of jug
v = capacity of cup
l = level
n = number of cups at that level
final_l = final level to which cups are to be filled for eg 5th level
initially
l = 1, n = 1;
%pernentage = (V - (l*n*v))/(final_l* final_l - l*n)
After filling the water to the cups at each level we can calculate the percentage of water to be filled in the cups at next level so that all the cups are covered, also store the value of % into an array
The solution is Morris Traversal i.e to do the inorder traversal without extra space, We just need to do inorder traversal using morris traversal till we find the median which can be n/2 for even count and (n-1)/2 when count is odd
- jerry April 18, 2017