[DP] Coloring of house

Problem Statement: There are a row of houses. Each house can be painted with three colors: red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost.

On reading the problem statement, the first approach that comes to mind is GREEDY approach. As soon as we see "minimum"  keyword, we start thinking in greedy way as we try to cut down our expenses in order to save more but that is not always the case.

Let us take an example, there are 4 houses and the color cost chart is as below:

	Red	Green	Blue
H1	12	19	8
H2	5	14	3
H3	8	14	15
H4	7	12	10

  
The thought process works like we start to pick the H1 with Blue i.e. 8, then H2 with Red i.e. 5, then h3 with Green i.e. 14 and finally H4 with Red i.e. 7 making the total up to 34.

But if i say H1 with Red (12), H2 with Blue (3), H3 with Red (8) and H4 with Blue (10) 
making a total of 33

So my greedy approach is failed!.

So next thing comes to muy mind is If i start with H2 and Blue, I might reach the minimum but again it will fail if the cost of coloring house H4 with Red would have been 5, then the cost using the first approach would have been 32.

So the problem we face is we do not know which house to consider as the start so that i get the minimum total.

lets formulate a mathematical formula to find the total cost of painting till house X

we will keep a 2D array, which store the total minimum cost if the house would be painted with Red, Green or blue.

	Red	Green	Blue
-	-	-	-
Hx-1	5	14	3
Hx	8+3	14+3	15+5
-	-	-	-

so the intermediate state looks something like this,
Hx-1 store the information that if Hx-1 would be painted with Red, the minimum cost till now will be 5, if with Green minimum cost will be 14 and if with Blue minimum cost will be 3.
then for Hx, if painted with Red, cost will be 8(cost off painting with Red) + 3 (minimum cost till Hx-1 with blue which is the lowest among Green and Blue)
similarly, if painted with Green cost would be 14+3
        and, if painted with Blue cost would be 15+5

so the formula becomes,

coloring House Hx with Red = Hx(Red) + Min(  Hx-1(Green) , Hx-1(Blue)  )
and find the minimum of cost among the three color and that is the answer.

Linked List

A linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a link to the next node in the sequence.

                     
 
Linked lists are one of the most common and simple data structure. It is used i creating lists, stacks, queues, dictionaries and many other abstract data types.

Pros:
  1. It is a dynamic data structure. The memory is created at run time while running a program.
  2. Insertion and deletion nodes operations are very easy in linked list. We can insert node and delete node easily.
  3. Linear data structures such as stacks and queues can be easily implemented using linked list.
  4. The access time is faster in linked list and it can be expanded in constant time without memory overhead.

Cons:
  1. Wastage of memory takes place in linked list as pointers requires extra memory for storage.
  2. In Linked list no random access is given to user, we have to access each node sequentially.
  3. In linked list, it takes a lot of time to access an element as individual nodes are not stored in contiguous memory allocations.
  4. Reverse traversing is very difficult in linked list.

 We can discuss about various simple operations applicable to linked list.

1. Traverse:

We keep on traversing the each and every node till we find the next link to point to null.

                                           while(node.next!=null)
                                           {
                                                 System.out.print(node.data);
                                                 node = node.next;
                                           }
                                           System.out.print(node.data);

2. Append node:

We keep on traversing till the end and then create a new node and provide the link of the lst node to the newly created node and point the link of newly created node to null.

                                       while(node.next!=null){
                                             node= node.next;
                                       }
                                       node.next = new Node(data);



3. Add a node after a specific node:

Keep on traversing till you find the node, then create a node and assign the next link to the current nodes next and then current nodes next to newly created node.

Adding 60 after 15

                                    while(node.next!=null){
                                          if(node.data==afterData){
                                                  Node temp = new Node(data,node.next);
                                                  node.next = temp;
                                                  break;
                                          }
                                          node = node.next;
                                   }

4. Remove node at the end:

This is a bit tricky, we can not traverse by checking for node's next to be null as to remove a node we need a reference to the node previous of the node to be deleted. So we check node.next.next!=null while traversing as there is no way to reach the previous node from the last node.

                                        if(node.next==null){
                                             head = null;
                                         }
                                        while(node.next.next!=null){
                                             node=node.next;
                                         }
                                        node.next=null;

Find no. with odd no of occurence in a sequence

The problem statement states that in a given sequence of number only 1 number is occurring odd no of times and rest all the numbers are occurring even no of time.
input e.g.
                  2,3,4,1,1,2,4
                  7,5,2,3,4,4,1,2,7,7,3,4,7,5

Please try this once before proceeding ahead.

We will discuss 2 approaches to solve the problem.

Approach 1 (storing no of count in a data structure) :

We can have a hash map which stores the number of occurrence of each number in the list.
Then we can count the number of occurrence and which one is odd.

Lets take an sample input as
          

2

3

1

1

4

2

3

4

3

if we try to process this input in a hash map then we can find following map

Key	Count
2	2
3	3
1	2
4	2

we can traverse the complete map to find out the count and which one is odd.

Pros:
  1. Its simple to think as well as code
Cons:
  1. It take more space
  2. 2 iterations required; 1st iteration for counting,  2nd iteration on the map to check whose count is odd

You can find the complete source code here.
For this special case when only one item is occurring odd no of time, we can use XOR operation as well.

Approach 2 (XOR operation) :

In this approach we will XOR all the items and the final output will be the number which occurs odd no of times.

e.g.

2

3

1

1

4

2

3

4

3

                                                             
here number = 2^3^1^1^4^2^3^4^3 = 3

This solutions works only when you have a single number occurring odd no of times.

You can find the complete source code here.