FastPrep

Description

Solutions

Rob Houses Without Getting Caught

🤘 INTERN📚RELATED PROBLEMS

You are a robber and you need to rob houses, the number of houses you need to rob are denoted by y and total number of houses that are there are denoted by n.

You must not get caught and rob y houses, to not get caught, the total distance you travelled should be a multiple of an integer denoted by x. The array a is given where a[i] denotes the distance between two houses. You cannot rob the house you have already robbed and you can start from anywhere to start robbing.

Return the total number of ways you can rob houses without getting caught.

Example 1:

Input:  n = 4, y = 3, x = 6, a = [4, 3, 5]
Output: 4 
Explanation:
      
      The possible ways to rob houses without getting caught, where the total distance travelled is a multiple of x are:
      
      
        1->2->4 with a total distance of 4+3+5 = 12, which is a multiple of 6.
        1->3->4 with a total distance of 4+5+3 = 12, which is a multiple of 6.
        4->2->1 with a total distance of 5+3+4 = 12, which is a multiple of 6.
        4->3->1 with a total distance of 5+4+3 = 12, which is a multiple of 6.
      
      
      Therefore, there are 4 ways to rob the houses without getting caught.

Constraints:

N/A