House Robber
Mr. X is a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden. All houses along this street are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

You are given an array/list of non-negative integers 'ARR' representing the amount of money of each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.

Note:

It is possible for Mr. X to rob the same amount of money by looting two different sets of houses. Just print the maximum possible robbed amount, irrespective of sets of houses robbed.

For example:

(i) Given the input array arr[] = {2, 3, 2} the output will be 3 because Mr X cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. So, he’ll rob only house 2 (money = 3) (ii) Given the input array arr[] = {1, 2, 3, 1} the output will be 4 because Mr X rob house 1 (money = 1) and then rob house 3 (money = 3). (iii) Given the input array arr[] = {0} the output will be 0 because Mr. X has got nothing to rob.

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows. The first line of each test case contains an integer, ‘N’ representing the size of the first array/list. The second line of each test case contains 'N' single space-separated integers representing the array/list elements.

Output Format :

For each test case, print a single line containing a single integer denoting the maximum money that can be robbed in a separate line. The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

House Robber

Mr. X is a professional robber planning to rob houses along a street. Each house has a certain amount of money hidden. All houses along this street are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

You are given an array/list of non-negative integers 'ARR' representing the amount of money of each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.

Note:

It is possible for Mr. X to rob the same amount of money by looting two different sets of houses. Just print the maximum possible robbed amount, irrespective of sets of houses robbed.

For example:

(i) Given the input array arr[] = {2, 3, 2} the output will be 3 because Mr X cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. So, he’ll rob only house 2 (money = 3)

(ii) Given the input array arr[] = {1, 2, 3, 1} the output will be 4 because Mr X rob house 1 (money = 1) and then rob house 3 (money = 3).

(iii) Given the input array arr[] = {0} the output will be 0 because Mr. X has got nothing to rob.

Input Format :

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains an integer, ‘N’ representing the size of the first array/list.

The second line of each test case contains 'N' single space-separated integers representing the array/list elements.

Output Format :

For each test case, print a single line containing a single integer denoting the maximum money that can be robbed in a separate line.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5 x 10 ^ 3
1 <= ARR[i] <= 10 ^ 9

Time limit: 1 sec.

Accepted Answer

The task is to find the maximum amount of money Mr. X can rob from houses arranged in a circle without alerting the police.

The problem can be solved using dynamic programming.
Create two arrays to store the maximum amount of money robbed when considering the first house and when not considering the first house.
Iterate through the array and update the maximum amount of money robbed at each house.
The final answer will be the maximum of the last element in both arrays.

Accepted Answer

Dynamic Programming

The main point is that you can't rob both the first and the last houses.

Therefore, the core idea is to apply dynamic programming. Two cases are considered here:

When you rob the first house
When you don't rob the first house, i.e. you rob the last one.

The dynamic programming algorithm that must be applied considering two arrays, given array ARR and new array DP to store value till the ith house is:

Initialize DP[0] to 0 and DP[1] = ARR[1]
Iterate over houses
At the ith house you have two options:
- Keep the money from the (i-1)th (previous) house, skipping the ith house, i.e. DP[i-1]
- Rob the ith house after the (i-2)th house, skipping the (i-1)th i.e. DP[i-2]+ARR[i]
Choose the most profitable option i.e. Maximum of DP[i-1] and DP[i-2] + ARR[i]
Return the sum you've got after the last house

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of houses.

Because we’ll be creating an auxiliary array to store the maximum amount robbed for every house.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array.

Because we’ll be traversing the entire array twice.

You are given an array/list of non-negative integers 'ARR' representing the amount of money of each house. Your task is to return the maximum amount of money Mr. X can rob tonight without alerting the police.

Note:

For example:

Input Format :

Output Format :

Note:

Constraints:

Top Paytm Full Stack Developer interview questions & answers

Popular interview questions of Full Stack Developer