Given a number N, now find the number of occurrences of each digit

Given a number N, now find the number of occurrences of each digit 0..9 from 0 to N
Ex:
i/p: 12
o/p:
2
5
2
1
1
1
1
1
1
1

Implementation:

class GivenNumberN_FindTheNumberOfOccurrencesOfEachDigit{
static int[] findOccurrences(int n){
if(n == 0)  //Base condition
return null;

if(n < 0)  //If number is negitive then make it positive.
n = n * (-1);

int []arr = new int[10];  //array to hold the occurrences of numbers
init(arr);  //initialize the array with zero
 
         arr[0]++;
for(int i = 1; i <= n; i++){  //loop till given number to find the occurrence
int temp = i;
while( temp > 0){    //find the occurrence of digit in current number - temp
int rem = temp % 10;  //get the last digit of current number
arr[rem]++;  //increment the count of digit
temp /= 10;
}
}
return arr;  //return the array of occurrence of number
}

static void init(int []arr){
for(int i = 0; i < 10; i++)
arr[i] = 0;
}

public static void main(String... args){
int n = 12;
int []count = findOccurrences(n);
System.out.println(java.util.Arrays.toString(count));
}
}

Create a mirror of a binary tree

Example
Input

Output

Implementation

public static Tree mirror(Tree root){

if(root == null)

return null;

Tree leftTree = null, rightTree = null;

if(root.left != null)

leftTree = mirror(root.left);

 

     if(root.right != null)

rightTree = mirror(root.right);

root.left = rightTree;

root.right = leftTree;

return root;

}

Find the merging point in given 2 linked lists

Example:
Input :







Output : 4

Algorithm
     1) Find lengths of both lists
     2) take the difference d of the lengths
     3) make d steps in longer list
     4) step in both lists in parallel until links to next node match

Implementation

class FindTheMergingPoingInGiven2LinkedList{
    static class LinkedList{
        int data;
        LinkedList next = null;
     
        public LinkedList(int data){
            this.data = data;
        }
     
        public void insertAtEnd(int data){
            LinkedList head = this;
            LinkedList newNode = new LinkedList(data);
         
            if(head == null){
                head = newNode;
                return;
            }
         
            while(head.next != null){
                head = head.next;
            }
            head.next = newNode;
        }
     
        public void print(LinkedList head){
            while(head != null){
                System.out.print(head.data + " ");
                head = head.next;
            }
            System.out.println();
        }
     
        //time : O(N)
        public static int length(LinkedList head){
            int length = 0;
            while(head != null){
                length++;
                head = head.next;
            }
            return length;
        }
                   
        public static LinkedList findMergingPoint(LinkedList head, LinkedList head2){
            //Base condition
            if(head == null && head2 == null)
                return null;
            
            int length = length(head);  //length of first list
            int length2 = length(head2);  //length of second list
            
            int diff;  //difference d of the lengths
            LinkedList bigList, smallList;
            if(length > length2){
                diff = length - length2;
                bigList = head;
                smallList = head2;
            }else{
                diff = length2 - length;
                bigList = head2;
                smallList = head;
            }
            
             //make d steps in longer list
            for(int i = 0; i < diff; i++)
                bigList = bigList.next;
            
            //make step in both lists in parallel until links to next node match      
           //or null     
            while(bigList != null && smallList != null){
                if(bigList == smallList) 
                    return bigList; 
                
                bigList = bigList.next;
                smallList = smallList.next;
            }
            return null;
        }
    }
 
    public static void main(String []args){
        LinkedList head = new LinkedList(1);
        head.insertAtEnd(2);
        head.insertAtEnd(3);
        head.insertAtEnd(4);
        head.insertAtEnd(5);
        head.insertAtEnd(6);
     
        LinkedList head2 = new LinkedList(7);
        head2.insertAtEnd(8);
        head2.next.next = head.next.next.next;     //merging the lists
     
     
        head2.print(head);
        head2.print(head2);
     
        LinkedList mergePoint = LinkedList.findMergingPoint(head, head2);
        System.out.println(mergePoint.data);
    }

}

Time Complexity: O(max(m, n))
Space Complexity : O(1)

Substract two numbers represented as linked list and return result as linked list

Example:
Input : 7->1->6 (617)
           5->9->2 (295)
Output : 2->2->3 (322)

class SubtractionOfLinkedList{
//List Node
static class Node{
int data;
Node next = null;

public Node(int data){
this.data = data;
}

//insert in list at end
public void insert(int data){
Node n = this;
Node newNode = new Node(data);

while(n.next != null){
n = n.next;
}
n.next = newNode;
}

//Utility function to print the list
public static void print(Node n){
while(n != null){
if(n.next == null)
System.out.println(n.data);
else
System.out.print(n.data + "->");
n = n.next;
}
}
}

//Utility function to subtract given lists
static Node subtract(Node n1, Node n2, int borrow){
                  //Base condition
if(n1 == null && n2 == null && borrow == 0)
return null;

Node result = new Node(borrow);
int value = borrow;
 
                  if(n1.data >= n2.data){
value += n1.data - n2.data;
borrow = 0;
}else{
if(n1.next != null){
value += (n1.data)+10 - n2.data;
borrow = -1;
}else{
value += (n1.data)+10 - n2.data;
value = value*(-1);
borrow = 0;
}
}
result.data = value;
 
  //Recurse
if(n1.next!=null || n2.next!=null || borrow<0){
Node more = subtract(n1.next != null ? n1.next : null,
                                                      n2.next != null ? n2.next : null,
                                                      borrow < 0 ? -1 : 0);

result.next = more;
}
return result;
}

public static void main(String... args){
Node n1 = new Node(7);
n1.insert(1);
n1.insert(6);

Node n2 = new Node(5);
n2.insert(9);
n2.insert(2);

Node result = subtract(n1, n2, 0);
Node.print(result);
}
}

Output : 2->2->3

Naive Pattern Searching Algorithm

class StringMatchingAlgorithms{
static boolean isFoundHelper(char[] target, char[] pattern){
int targetLen = target.length;
int patternLen = pattern.length;
int k,l;
for(int i = 0; i < targetLen-patternLen+1; i++){
k = 0;l = i;
for(int j = 0; j < patternLen; j++){
if(target[l] == pattern[j]){
k++;l++;
                          }else
break;
}
if(k == patternLen)  //Pattern found, return true
                           return true;
}
return false;
}

static boolean isFound(String s, String p){
return isFoundHelper(s.toCharArray(), p.toCharArray());
}

public static void main(String []args){
String source = "abcdefab";
String pattern = "cde";

System.out.println("Result : "+isFound(source, pattern));
}
}

Time Complexity : O(N^2)
Space Complexity : O(1)

Combinations of coins

Write a function that takes an integer number and return the count of unique combinations of coins.
(Note : coins = {1, 2, 5, 10})
Example
Input : 3
Output : 2 (because we can make 3 by 1+1+1 or 1+2)

Input : 5
Output : 4 (because we can make 5 by 1+1+1+1+1, 1+1+1+2, 1+2+2, 5)

Implementation

class MakeChange{
static int makeChange2(int n, int denom){
//Base condition
if(n == 0)
return 1;

if(n < 0 || denom == 0)
return 0;

int nextDenom = getNextDenom(denom); //get the next denominator
//either take the current denominator or eliminate it
return makeChange2(n - denom, denom) + makeChange2(n, nextDenom);
}

//Utility function to get the next denominator
static int getNextDenom(int denom){
if(denom == 1)
return 2;
else if(denom == 2)
return 5;
else if(denom == 5)
return 10;
else
return 0;
}

public static void main(String... args){
int n = 5;
int change = makeChange2(n, 1);
System.out.println(change);
}
}

Rotate the array

Example
Input : {1, 2, 3, 4, 5},  rotate Index = 2
Output: {3, 4, 5, 1, 2}

Algorithm :
   1. Divide the given array into 2 groups at given rotate-index.(Group-A and Group-B)
   2. Group-A' = Reverse first group Group-A.
   3. Group-B' = Reverse second group Group-B.
   4. Reverse {Group-A', Group-B'}

How?:
let us consider the array = {1, 2, 3, 4, 5} and rotated index = 2.
then Group-A = {1, 2}
Group-B ={3, 4, 5}
{1, 2, 3, 4, 5} = {Group-A, Group-B}

Now reverse first group Group-A :
  Group-A' = reverse(Group-A)
  Group-A' = {2, 1}

Now reverse second group Group-B :
  Group-B' = reverse(Group-B)
  Group-B' = {5, 4, 3}

Now reverse {Group-A' , Group-B'} = {3, 4, 5, 1, 2}

Implementation

class RotateArray{
        public static void rotate(int []a, int k){
               reverse(a, 0, k-1);   //reverse the first group
               reverse(a, k, a.length - 1);   //reverse the second group
               reverse(a, 0, a.length - 1);  //reverse the array
        }
    
        public static void reverse(int []a, int start, int end){
               if( a.length < end-start)
                     return;
        
               for(; start < end; start++, end--){
                     int t = a[end];
                     a[end] = a[start];
                     a[start] = t;
               }
        }
    
        public static void main(String []args){
               int []a = {1,2,3,4,5};
               rotate(a,2);
              System.out.println(java.util.Arrays.toString(a));
        }  
}

Output : 3, 4, 5, 1, 2