ozkansari
BAN USER/*
* Recursive solution for getting nodes at a given distance
*/
public List<Node> getNodesAtDistance(Node rootNode, int distance) {
List<Node> resultList = new ArrayList<Node>();
if(rootNode==null) {
return resultList;
} else if(distance==0) {
resultList.add(rootNode);
} else {
Node left = rootNode.getLeft();
resultList.addAll(
getNodesAtDistance(left, distance-1) );
Node right= rootNode.getRight();
resultList.addAll(
getNodesAtDistance(right, distance-1) );
}
return resultList;
}
/**
* Problem: Given an integer, i,
* find whether it can be expressed as 2^k. Where k< i
*/
class PowerOf2Number {
/**
* Test
*/
public static void main(String[] args) {
int input = 262144; // 2^18
System.out.println( isPowerOf2Number_1(input) );
System.out.println( isPowerOf2Number_2(input) );
System.out.println( isPowerOf2Number_3(input) );
System.out.println( isKthPowerOf2Number(input,18) );
}
/**
* Time complexity: O(32)=O(1)
* Space complexity : 0(1)
*/
private static boolean isPowerOf2Number_1(int input){
if(input==0) return false;
if(input<0) input=-1*input;
int temp = 1;
for (int i=0;i<=32;i++) {
if (temp==input) {
return true;
}
temp= temp<<1;
}
return false;
}
/**
* Time complexity: O(1)
* Space complexity : 0(1)
*/
private static boolean isPowerOf2Number_2(int input){
if(input==0) return false;
if(input<0) input=-1*input;
int result = input&(input-1);
return result==0;
}
/**
* Time complexity: O(log n)
* Space complexity : 0(1)
*/
private static boolean isPowerOf2Number_3(int input) {
if(input<0) input=-1*input;
if(input==1) return true;
while (input > 2 && input % 2 == 0) {
input = input / 2;
}
return (input == 2);
}
/**
* Time complexity: O(1)
* Space complexity : 0(1)
*/
private static boolean isKthPowerOf2Number(int input, int k){
return ( (1<<k) == input) ;
}
}
- ozkansari January 06, 2013