CareerCup

Max Heap

public static void main(String[] args) {
        System.out.println(nestedList_LeetCode_364("[1,1[1,[1,1],1,[1]]]".toCharArray()));
    }


    public static int nestedList_LeetCode_364(char[] string) {
        int sum = 0;
        Stack<String> stack = new Stack<>();
        int index = 0;
        int level = 0;
        while (index < string.length) {
            if (Character.isDigit(string[index]) || string[index] == '[') {
                stack.push("" + string[index]);
                if (string[index] == '[') {
                    level = Math.max(1, level - 1);
                }
            } else if (string[index] == ']' && !stack.isEmpty()) {
                int tempSum = 0;
                while (!stack.isEmpty() && !stack.peek().equals("[")) {
                    tempSum = tempSum + Integer.valueOf(stack.pop());
                }
                sum = sum + (tempSum * level++);
                stack.pop();
            }
            index++;
        }
        return sum;
    }

Can anybody offer a better solution pls ? Please don't change the method signature

public static void main(String[] args) throws Exception {
        System.out.print(swiggySDE3(Arrays.asList("(A,B)", "(B,C)", "(A,D)", "(C,E)", "(A,F)")));
    }

    public static String swiggySDE3(List<String> str) {
        Map<String, List<String>> map = new HashMap<>();
        for (String t : str) {
            String[] pair = t.substring(1, t.length() - 1).split(",");
            final List<String> orDefault = map.getOrDefault(String.valueOf(pair[0]), new ArrayList<>());
            orDefault.add(pair[1]);
            map.put(pair[0], orDefault);
        }
        StringBuffer stringBuffer = new StringBuffer();
        swiggySDE3UTIL("A", map, stringBuffer);
        return stringBuffer.toString().substring(0, stringBuffer.length()-1);
    }

    private static void swiggySDE3UTIL(String start, Map<String, List<String>> map, StringBuffer stringBuffer) {
        final List<String> values = map.get(start);
        if (values == null || values.isEmpty()) {
            stringBuffer.append(start + ")");
            return;
        }
        stringBuffer.append(start+"(");
        values.forEach(t->swiggySDE3UTIL(t,map,stringBuffer));
        stringBuffer.append(")");
    }

Apply rolling hash

public boolean repeatedSubstringPattern(String s) {
		int prefixTable[] = new int[s.length()];
		int i = 0;
		int j = 1;
		while (j < s.length()) {
			if (s.charAt(i) == s.charAt(j))
				prefixTable[j++] = ++i;
			else if (i > 0)
				i = prefixTable[i - 1];
			else
				j++;
		}
		return prefixTable[s.length() - 1] > 0 && s.length() % (s.length() - prefixTable[s.length() - 1]) == 0;
	}

KMP prefix table algorithm can help

public static int smallestSubarray(int arr[], int target) {
		int minLen = Integer.MAX_VALUE;
		int end = 0;
		int rollingSum = 0;
		Map<Integer, Integer> pos = new HashMap<Integer, Integer>();
		while (end < arr.length) {
			rollingSum = rollingSum + arr[end];
			if (pos.containsKey(rollingSum % 16) && rollingSum >= target) {
				minLen = Math.min(minLen, end - (pos.get(rollingSum % 16)));
			}
			pos.put(rollingSum % 16, end);
			end++;
		}
		return minLen;
	}

What about this solution.

We maintain a rolling hash map(productId,sumOfSoldQuantiesTillNow)
For each time slot, We store the map of (products,sumOfSoldQuantiesTillNow)
which can be retrieved later.

time hour1:
hour1_map={(p1,34),(p2,23),(p3,12),(p4,17),(p6,12)}


time hour2:
hour2_map=hour1_map+{(p1,3),(p2,14),(p3,8),(p4,34),(p5,12)}


time hour3:
Here, we can calculate the count of product sold of time_hour2 simply
by subtraction and take out top K

static class TreeNode {
		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + ((children == null) ? 0 : children.hashCode());
			result = prime * result + data;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			TreeNode other = (TreeNode) obj;
			if (children == null) {
				if (other.children != null)
					return false;
			} else if (!children.equals(other.children))
				return false;
			if (data != other.data)
				return false;
			return true;
		}

		TreeNode(int data) {
			this.data = data;
		}

		@Override
		public String toString() {
			return this.data + "";
		}

		int data;
		List<TreeNode> children;

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public List<TreeNode> getChildren() {
			return children;
		}

		public void setChildren(List<TreeNode> children) {
			this.children = children;
		}
	}


	public static void main(String args[]) throws Exception {
          Node root=new Node(2);
          root.left=new Node(1);
          root.right=new Node(1);
          List<TreeNode> temp=findDuplicateSubtrees(root);
	}

	public static List<TreeNode> findDuplicateSubtrees(Node root) {
		String inOrder = inOrderTraversal(root);
		String preOrder = preOrderTraversal(root);
		List<TreeNode> list = new ArrayList<TreeNode>();
		for (int i = 0; i < inOrder.length(); i++) {
			for (int j = i; j < inOrder.length(); j++) {
				String subStr = inOrder.substring(i, j);
				if (inOrder.indexOf(subStr)  != inOrder.lastIndexOf(subStr)
				 && preOrder.indexOf(subStr) != preOrder.lastIndexOf(subStr) && subStr.length()>0) {
					list.add(new TreeNode(Character.getNumericValue(subStr.charAt(0)))) ; 
				}
			}
		}
		return list;
	}

	private static String preOrderTraversal(Node root) {
		if (root == null)
			return "";
		return root.data + preOrderTraversal(root.left) + preOrderTraversal(root.right);
	}

	private static String inOrderTraversal(Node root) {
		if (root == null)
			return "";
		return inOrderTraversal(root.left) + root.data + inOrderTraversal(root.right);
	}

public static void main(String args[]) throws Exception {
		String words[] = { "cc", "cb", "bb", "ac" };
		char ordering[] = { 'b', 'c', 'a' };
		System.out.println(checkIfSortedArray(words, ordering));
	}

	public static boolean checkIfSortedArray(String strs[], char orderings[]) {
		Map<Character, Integer> map = new HashMap();
		for (int i = 0; i < orderings.length; i++) {
			map.put(orderings[i], i);
		}
		for (int i = 1; i < strs.length; i++) {
			int mismatch = getFirstMismatch(strs[i - 1], strs[i]);
			if (mismatch != -1) {
				char from = strs[i - 1].toCharArray()[mismatch];
				char to = strs[i].toCharArray()[mismatch];
				if (map.get(from) > map.get(to))
					return false;
			}
		}
		return true;
	}

	public static int getFirstMismatch(String str1, String str2) {
		char elem[] = str1.toCharArray();
		char elem2[] = str2.toCharArray();
		return IntStream.range(0, min(elem.length, elem2.length)).filter(temp -> elem[temp] != elem2[temp]).findFirst()
				.orElse(-1);
	}

public static void main(String args[]) throws Exception {
		String words[] = { "cc", "cb", "bb", "ac" };
		char ordering[] = { 'b', 'c', 'a' };
		System.out.println(checkIfSortedArray(words, ordering));
	}

	public static boolean checkIfSortedArray(String strs[], char orderings[]) {
		Map<Character, Integer> map = new HashMap();
		for (int i = 0; i < orderings.length; i++) {
			map.put(orderings[i], i);
		}
		for (int i = 1; i < strs.length; i++) {
			int mismatch = getFirstMismatch(strs[i - 1], strs[i]);
			if (mismatch != -1) {
				char from = strs[i - 1].toCharArray()[mismatch];
				char to = strs[i].toCharArray()[mismatch];
				if (map.get(from) > map.get(to))
					return false;
			}
		}
		return true;
	}

	public static int getFirstMismatch(String str1, String str2) {
		char elem[] = str1.toCharArray();
		char elem2[] = str2.toCharArray();
		return IntStream.range(0, min(elem.length, elem2.length)).filter(temp -> elem[temp] != elem2[temp]).findFirst()
				.orElse(-1);
	}

@sudip.innovates or @cemaivaz

Can you please explain how does the problem boil down to dp[i-1]+dp[i-2]?

DP comes into picture only when there are overlapping sub-problems.It can be done through iterative BFS as well.

public static void main(String args[]) throws Exception {
		int arr[] = { 2, 3, 4, 0, 1 };
		// int arr[] = { 0, 1, 2, 3, 4 };
		System.out.println(detectCycle(arr));
	}

	public static boolean detectCycle(int arr[]) {
		final int N = arr.length;
		int index = 0;
		while (index < N) {
			while ((!(arr[index % N] / N > 1)) && index < N) {
				if (index != arr[index % N]) {
					int temp1 = arr[index] % N;
					arr[index % N] = arr[index % N] + N;
					index = temp1;
				} else {
					index++;
				}
			}
			index++;
		}
		if (Arrays.stream(arr).max().getAsInt() / N > 1)
			return true;
		return false;
	}

This is a plain DFS problem using recursion/iteration.
However, it gets a deal if you can do it without space.We can optimise space by using a bit array.

@Trutgeek, does it work for 2->4->3->1->8 ?

static class Node {
		Node(int data) {
			this.data = data;
		}

		@Override
		public String toString() {
			return this.data + " ";
		}

		int data;
		Node left;
		Node right;
		Node next;
	}
	
	public static void main(String args[]) throws Exception {
		int arr[] = { 4, 2, 1, 3, 6, 5, 7 };
		Node root = builtTreeFromPreOrder(arr);
		System.out.println(root);
	}

	public static Node builtTreeFromPreOrder(int arr[]) {
		Stack<Node> stack = new Stack<Node>();
		Node root = new Node(arr[0]);
		stack.push(root);
		int index = 1;
		while (index < arr.length) {
			if (!stack.isEmpty() && stack.peek().data > arr[index]) {
				Node temp = new Node(arr[index]);
				stack.peek().left=temp;
				stack.push(temp);
				index++;
			} else {
				Node temp = null;
				while (!stack.isEmpty() && stack.peek().data < arr[index]) {
					temp = stack.pop();
				}
				if (temp != null) {
					Node temp1 = new Node(arr[index]);
					temp.right = temp1;
					stack.push(temp1);
					index++;
				}
			}
		}
		return root;
	}

public static void main(String args[]) throws Exception {
		int K = 3;
		System.out.println(isDivisibleByKInBase("1010100011", K, 2));
	}

	private static int isDivisibleByKInBase(String str, int K, int base) {
		char c[] = new StringBuilder(str).reverse().toString().toCharArray();
		int rem = 0;
		for (int i = 0; i < c.length; i++) {
			rem = ((((int) Math.pow(base, i) * Integer.parseInt("" + c[i])) % K) + rem) % K;
		}
		return rem;
	}

public static void main(String args[]) throws Exception {
		int K = 5;
		System.out.println(isBinaryDivisible(Long.toBinaryString(655515), K));
	}

	private static boolean isBinaryDivisible(String binaryString, int K) {
		char c[] = new StringBuilder(binaryString).reverse().toString().toCharArray();
		int rem = 0;
		for (int i = 0; i < c.length; i++) {
			rem = ((((int) Math.pow(2, i) * Integer.parseInt("" + c[i])) % K) + rem) % K;
		}
		return rem == 0;
	}

This is as simple as building a TRIE out of incoming words and storing the start index at the leafs.

Put all the nodes in a min-heap.Keep extracting the root and populating the random pointer with the next extracted root from heap.

Space: O(N)
Time : O(NLogN)

It's a clear application of TRIE and DFS

careercup.com/question?id=5691748142546944

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static class LList {
		LList(int data) {
			this.data = data;
		}

		LList(int data, LList down, LList next) {
			this.data = data;
			this.down = down;
			this.next = next;
		}

		LList() {
			this.data = Integer.MAX_VALUE;
		}

		@Override
		public String toString() {
			return " " + this.data + " ";
		}

		int data;
		LList next;
		LList prev;
		LList rand;
		LList down;
	}

	public static void main(String args[]) throws Exception {
		LList head = new LList(1);
		head.next = new LList(2);
		head.next.next = new LList(3);
		//head.next.next.next = new LList(4);
		updateLinkedList(head);
	}

	public static LList updateLinkedList(LList head) {
		LList temp = head;
		LList prev = null;
		LList slow = head;
		LList fast = head;
		Stack<LList> stack = new Stack<LList>();
		int len = 0;
		while (temp != null) {
			temp = temp.next;
			len++;
		}
		while (slow != null && fast != null) {
			prev = slow;
			stack.push(slow);
			slow = slow.next;
			fast = fast.next;
			if (fast != null)
				fast = fast.next;
		}
		if (len % 2 == 0)
			prev = prev.next;
		while (!stack.isEmpty()) {
			prev.data = stack.pop().data + prev.data;
			prev = prev.next;
		}
		return head;
	}
}

public static void main(String args[]) throws Exception {
		int arr[] = { 1, 2, 3, 4, 9, 5, 6 };
		nextHigherElem(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static int[] nextHigherElem(int arr[]) {
		int op[] = new int[arr.length];
		Stack<Integer> stack = new Stack<Integer>();
		for (int i = arr.length - 1; i >= 0; i--) {
			while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
				stack.pop();
			}
			if (!stack.isEmpty()) {
				op[i] = arr[stack.peek()];
			} else {
				op[i] = -1;
			}
			stack.push(i);
		}
		System.arraycopy(op, 0, arr, 0, arr.length);
		return arr;
	}

static class HeapNode {
		char c;
		int count;

		public HeapNode(char c, int count) {
			this.c = c;
			this.count = count;
		}

		public char getC() {
			return c;
		}

		public void setC(char c) {
			this.c = c;
		}

		public int getCount() {
			return count;
		}

		public void setCount(int count) {
			this.count = count;
		}

		@Override
		public int hashCode() {
			final int prime = 31;
			int result = 1;
			result = prime * result + c;
			return result;
		}

		@Override
		public boolean equals(Object obj) {
			if (this == obj)
				return true;
			if (obj == null)
				return false;
			if (getClass() != obj.getClass())
				return false;
			HeapNode other = (HeapNode) obj;
			if (c != other.c)
				return false;
			return true;
		}

		@Override
		public String toString() {
			return "HeapNode [c=" + c + ", count=" + count + "]";
		}

	}

	public static String arrange(String str) {
		int count[] = new int[26];
		int max = Integer.MIN_VALUE;
		for (char c : str.toCharArray()) {
			count[c - 'a'] = count[c - 'a'] + 1;
			if (max < count[c - 'a']) {
				max = count[c - 'a'];
			}
		}
		if (max > ((str.length() / 2) + 1)) {
			System.out.println("Can't be done");
			return "";
		}
		char c = 'a';
		PriorityQueue<HeapNode> maxHeap = new PriorityQueue<HeapNode>(new Comparator<HeapNode>() {
			@Override
			public int compare(HeapNode o1, HeapNode o2) {
				return o2.count - o1.count;
			}
		});
		for (int i = 0; i < count.length; i++) {
			if (count[i] != 0) {
				HeapNode node = new HeapNode(c++, count[i]);
				maxHeap.add(node);
			}
		}
		StringBuffer sbf = new StringBuffer();
		HeapNode temp = null;
		while (!maxHeap.isEmpty()) {
			HeapNode node = maxHeap.poll();
			sbf.append(node.c);
			node.count--;
			if (temp != null && temp.count > 0) {
				maxHeap.add(temp);
			}
			temp = node;
		}
		return sbf.toString();
	}

	public static void main(String args[]) throws Exception {
		System.out.println(arrange("abcaabddddd"));
	}

Store the number the people in an array of long ages[]=new long[150], assuming 150 of max age.For each incoming age, we can update corresponding index and increment by 1.

We can actually leverage segment tree here for better performance.

@ChrisK ..Can you tell me why it is like max(dp(len(array)-1), dp(len(array)-2) ?

public static void main(String args[]) throws Exception {
		int arr[] = { 1, 1, 1, 5 };
		System.out.println(maxValue(arr));
	}

	public static int maxValue(int arr[]) {
		int matr[][] = new int[arr.length][arr.length];
		for (int index = 0; index < arr.length; index++)
			matr[index][index] = arr[index];
		for (int len = 2; len <= arr.length; len++) {
			for (int i = 0; i < arr.length - len + 1; i++) {
				int j = i + len - 1;
				for (int k = i + 1; k <= j; k++) {
					matr[i][j] = max(matr[i][j], matr[i][k - 1] + matr[k][j], matr[i][k - 1] - matr[k][j], matr[i][k - 1] * matr[k][j]);
				}
			}
		}
		return matr[0][arr.length - 1];
	}

	public static int max(int... arr) {
		return Arrays.stream(arr).max().getAsInt();
	}

def printCombination(list, index, op, K, sum, sumTillNow):
    if sumTillNow == sum and len(op) == K:
       print(op);
       return;
    if index >= len(list) or len(op) > K or sumTillNow > sum :
       return;   
    op.append(list[index]);
    printCombination(list, index + 1, op, K, sum, sumTillNow + list[index]);
    op.pop();
    printCombination(list, index + 1, op, K, sum, sumTillNow);

printCombination([1, 2, 3, 4, 5], 0, [], 4, 14, 0);

def printCombination(list, index, op, K, sum, sumTillNow):
    if sumTillNow == sum and len(op) == K:
       print(op);
       return;
    if index >= len(list) or len(op) > K or sumTillNow > sum :
       return;   
    op.append(list[index]);
    printCombination(list, index + 1, op, K, sum, sumTillNow + list[index]);
    op.pop();
    printCombination(list, index + 1, op, K, sum, sumTillNow);

printCombination([1, 2, 3, 4, 5], 0, [], 2, 6, 0);

def setNearestMinimum(arr):
    op = [99 for x in xrange(len(arr))];
    stack = [];
    for pos in xrange(len(arr)):
        if len(stack) == 0 or pos == 0:
           op[pos] = min(op[pos], -1);
           stack.append(pos); 
        else:
            while len(stack) > 0 and arr[stack[-1]] > arr[pos]:
                  stack.pop();  
            op[pos] = min(op[pos], stack[-1] if len(stack) > 0 else -1);
            stack.append(pos);
            
    stack = [];
    for pos in xrange(len(arr) - 1, -1, -1):
        if len(stack) == 0 or pos == len(arr) - 1:
           if op[pos] == -1: 
              op[pos] = min(op[pos], -1);
           stack.append(pos); 
        else:
            while len(stack) > 0 and arr[stack[-1]] > arr[pos]:
                  stack.pop();
            if op[pos] == -1:        
               op[pos] = stack[-1];
            else:
               op[pos] = stack[-1] if stack[-1] - pos < pos - op[pos]  else op[pos];    
            stack.append(pos);         
            
    for pos in xrange(len(op)):
       if op[pos] == -1:
          print(-1);
       else:
         print(arr[op[pos]]);         
    return;

setNearestMinimum([1, 200, 30, 1000, -6]);

I sincerely suggest the poster of this question to do a brief google before posting such questions.
This is pretty standard interview question.

import math

def printPaths(N, path):
    if path[-1] == N:
       print(path);
    if path[-1] > N:
       return;      
    for idx in xrange(int(math.log(N,2))+1):
        path.append(int(path[-1] + math.pow(2, idx)));
        printPaths(N, path);
        path.pop();

printPaths(6, [0]);

class LinkedListNode:
    def __init__(self, initdata):
        self.data = initdata
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setData(self, newdata):
        self.data = newdata

    def setNext(self, newnext):
        self.next = newnext
        
node1 = LinkedListNode(1);
node2 = LinkedListNode(2);
node3 = LinkedListNode(3); 
node4 = LinkedListNode(4);
node5 = LinkedListNode(5); 
node6 = LinkedListNode(6);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;            
        
def countGroups(list, head):
    nodes = set(list);
    count = 0;
    while not head == None:
          if head.data in nodes:      
             count += 1;
          while not head == None and head.data in nodes:
                nodes.remove(head.data);
                head = head.next;
          if not head == None:      
             head = head.next;
    return count;       
print(countGroups([1,2, 3, 4, 5, 6], node1));

@aonecoding - I do understand your code is working.But can you explain me a bit the logic, please?

def nearestCElem2K(list, K, C):
    pos = binarySearch(list, K);
    op = []
    opIndex=999999;
    i = pos - 1;
    j = pos;
    count = 0;
    while count < C and i >= 0 and j < len(list):
          if abs(list[i] - K) < abs(list[j] - K):
             op.append(list[i]);
             opIndex=min(i,opIndex); 
             i = i - 1; 
          else:
             op.append(list[j]);  
             j = j + 1;
          count = count + 1;
          
    while count < C and i >= 0:
          op.append(list[i]);
          opIndex=min(i,opIndex);
          i = i - 1;
          count = count + 1; 
    while count < C and j < len(list):
          op.append(list[j]);
          j = j + 1;
          count = count + 1;
    print(op);                          
    return list[opIndex];

def binarySearch(list, K):
    st = 0;
    end = len(list) - 1;
    while st < end:
          mid = st + ((end - st) / 2);
          if list[mid] == K:
             return mid;
          if list[mid] < K:
             st = mid + 1;
          else:
             end = mid - 1;      
    return st;          
 
print(nearestCElem2K([1,2,5,8,9,13],8,4));

@Fernando ... Can we do better? O(n^2) is an obvious solution.

@ChrisK..My solution finds the largest rectangle

In such scenarios, TRIE is the best data structure for storing the contacts.

def largestRectangleInMatr(list):
    arr = [0 for x in range(0, len(list[0]))];
    largestRecArea = 1;
    for idx1 in range(0, len(list)):
        for idx2 in range(0, len(list[idx1])):
            arr[idx2] = 0 if list[idx1][idx2] == 0 else arr[idx2] + list[idx1][idx2];
        largestRecArea = max(largestRecArea, computHistArea(arr));    
    return largestRecArea;

def computHistArea(arr):
    stack = [];
    area = 1;
    idx = 0;
    while idx < len(arr):
        if len(stack) == 0 or arr[stack[len(stack) - 1]] <= arr[idx]:
           stack.append(idx);
           idx = idx + 1; 
        else:
            width = stack.pop();
            area = max(area, ((arr[width] * idx)  if len(stack) == 0 else  (arr[width] * (idx - stack[len(stack) - 1] - 1))));
    idx = len(arr);      
    while len(stack) > 0:
          width = stack.pop();  
          area = max(area, ((arr[width] * idx)  if len(stack) == 0 else  (arr[width] * (idx - stack[len(stack) - 1] - 1))));     
    return area;            
 
print(largestRectangleInMatr([[1, 0, 0, 1, 1, 1],
                              [1, 0, 1, 1, 0, 1],
                              [0, 1, 1, 1, 1, 1],
                              [0, 0, 1, 1, 1, 1]]));

def printLongestCycle(list):
    visited = [0 for x in range(len(list))];
    maxLen = 1;
    for idx in xrange(len(list)):
        lenCurr = 0;
        while visited[idx] == 0:
              visited[idx] = 1;
              idx = list[idx];
              lenCurr = lenCurr + 1;
        maxLen = max(lenCurr, maxLen);
    return maxLen;

print(printLongestCycle([1, 2, 3, 4, 0, 5]));

@Naman Dasot: Can you explain your logic, please?

import Queue

def printJumbled(N):
    q = Queue.Queue(N);
    for idx in xrange(1, 10):
        q.put(idx);
    while not q.empty():
          item = q.get();
          print(item);
          lastElem = (item % 10);
          if lastElem > 1 and ((10 * item) + (lastElem - 1)) <= N:
             q.put((10 * item) + (lastElem - 1));
          if lastElem < 9 and ((10 * item) + (lastElem + 1)) <= N:
             q.put((10 * item) + (lastElem + 1));    
              
printJumbled(999);

The leaf need not be necessary a descendant of the target node.The path to nearest leaf can go through the parent of the target node also.We need to consider all such scenarios.

public static void main(String args[]) throws Exception {
		System.out.println(minSumOfSquares(37));
	}

	public static int minSumOfSquares(int N) {
		int arr[] = new int[N + 1];
		Arrays.fill(arr, Integer.MAX_VALUE);
		arr[0] = 0;
		arr[1] = 1;
		arr[2] = 2;
		for (int i = 3; i <= N; i++) {
			double sqrt = Math.sqrt(i);
			int x = (int) sqrt;
			if (Math.pow(sqrt, 2) == Math.pow(x, 2)) {
				arr[i] = 1;
				continue;
			}
			for (int j = 1; j <= Math.sqrt(i); j++) {
				arr[i] = Math.min(arr[i], arr[(int) (i - Math.pow(j, 2))] + arr[(int) Math.pow(j, 2)]);
			}
		}
		System.out.println(Arrays.toString(arr));
		return arr[N];
	}

public static void main(String args[]) throws Exception {
		computeDecimal("10111111000111111111111111111111111");
	}

	public static void computeDecimal(String binary) {
		long binLen = binary.length();
		long decLen = (int) Math.ceil(Math.log(binLen) / Math.log(2))+4;
		char elems[] = binary.toCharArray();
		long sum = 0;
		long mod = 0;
		for (int i = elems.length - 1; i >= 0; i--) {
			long temp = ((long) (Math.pow(2, elems.length - 1 - i) * Integer.parseInt("" + elems[i])));
			sum = sum + temp;
			mod = (mod + (temp % 3)) % 3;
			System.out.printf("Decimal = %" + decLen + "d Binary = %" + binLen + "s Reminder = %d\n", sum, binary.substring(i), mod);
		}
	}

BFS is the way to go

public static void main(String args[]) throws Exception {
		encryptString("abcd", "", 0);
	}

	private static void encryptString(String str, String result, int start) {
		if (start >= str.length()) {
			p(result);
			return;
		}
		int lastDigit = -1;
		if (result != null && result.length() > 0 && Character.isDigit(result.toCharArray()[result.length() - 1])) {
			lastDigit = result.toCharArray()[result.length() - 1];
		}
		if (lastDigit != -1) {
			char elem[] = result.toCharArray();
			elem[elem.length - 1] = (char) ((int) elem[elem.length - 1] + 1);
			encryptString(str, new String(elem), start + 1);
		} else {
			encryptString(str, result + 1, start + 1);
		}
		encryptString(str, result + str.toCharArray()[start], start + 1);
	}

	public static void p(String str) {
		System.out.println(str);
	}

public static void main(String args[]) throws Exception {
		System.out.println(divideWHTSign(300, 30));
	}

	public static int divideWHTSign(int a, int b) {
		int quotient = 0;
		while (a >= b) {
			quotient++;
			a -= b;
		}
		return quotient;
	}