House Robber Algorithm

In this post i will explain an interesting algorithm commonly called as House Robber Algorthim.Suppose a robber is planning to steal money from a group of houses.Amount of money each house is having is painted
on each house.But condition is he should not steal from adjacent house means , if he steals from nth house, he should
not steal from (n-1)th and (n+1)th house.How can he steal the maximum amount following the above condition.

We can solve this easily by using dynamic programming with recurssion.

Suppose we have houses in this order : House= 1, 2 , 3, 4 …. n
and A(House) is the amount in the House.

If we select a house with highest amount and start from there max(A(1),A(2),A(3)….) ,chances are we end with the less amount.
Hence for finding the best solution , we maintain 2 meta data at each house .Including(I) and Excluding(E)
Assume n=1,2,3… amount at each house,

I=n+ E(n-1)
E=max[I(n-1),E(n-1)]

After doing a recursive calculation at each house. Then the house with max(I,E) is the house to start the robbery.

Let me explain it more clearly by giving an example.

Algorithms to find missing number among 1 to n numbers

I was trying to find a missing number in 1 to n, which are stored in an array in any order. where n is a very big number. I came up with 3 approaches and their time complexities.

1. sort the list first using one of the sort algorithm and assume its time complexity is o(n) to sort it . then traverse the whole array and check if n+1 element is present for the nth element in the array. If not present then is the missing number. For traversing the time complexity can be o(n).So finally o(n)+o(n) =o(n)
2. Second approach i thought of is  finding the sum of 1 to n numbers using n*n(+1)/2 .then find the sum of the given numbers. Assuming the traversing complexity while doing the sum is o(n).Difference of both the sums gives the missing number.So finally it will be o(n)+o(n)=o(n). This is good if n is a small number , what it is some very big number . then sum will be very big which the data type in some languages cant hold.
3. I assume this is the best approach compared to above, we can use the XOR binary operation. we know (n XOR n) gives zero.like 1 XOR 1 =0,2 XOR 2 =0. So iterate the numbers and do the XOR operation of (1 to n ) and ( 1 to n with missing no). which gives the missing number .For iterating assume time complexity is o(n).