Maximize the money when no two adjacent Array indices can be chosen
Given an array of size N, each index has K amount of money, the target is to pick the maximum amount of money from the array but the constraint is that no two adjacent indices can be chosen.
Examples:
Input: N = 5, K = 10
Output: 30
Explanation: The possible option is to pick from the first,
third and fifth houses which will result in 30.Input: N = 2, K = 12
Output: 12
Explanation: The only choices are to pick
from the first or second which will result in 12.
Approach: The problem can be solved using the following observation:
There can be two cases:
- Case 1 (N is odd): You can either choose 1, 3, 5, . . . or 2, 4, 6, . . . In first case always count is one more than the second so, you choose first. Total indices that can be chosen = (N+1)/2
- Case 2 (N is even): You can either choose 1, 3, . . . or 2, 4, . . . In both case always count of elements is equal so you can choose any. Total indices chosen = N/2
Follow the steps to solve this problem:
- Check the parity of N:
- If N is odd, return (N+1)*K / 2
- Else, return N*K / 2
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the maximum // money thief can rob int maximizeMoney( int N, int K) { if (N & 1) return (N + 1) * K / 2; else return N * K / 2; } // Driver Code int main() { int N = 5, K = 10; // Function Call cout << maximizeMoney(N, K) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the maximum money thief can rob static int maximizeMoney( int N, int K) { if ((N & 1 ) != 0 ) { return (N + 1 ) * K / 2 ; } else { return N * K / 2 ; } } public static void main(String[] args) { int N = 5 , K = 10 ; // Function call System.out.println(maximizeMoney(N, K)); } } // This code is contributed by lokeshmvs21. |
Python3
# python3 code to implement the approach # Function to find the maximum # money thief can rob def maximizeMoney( N, K): if (N & 1 ): return (N + 1 ) * K / 2 else : return N * K / 2 # Driver Code N = 5 K = 10 print (maximizeMoney(N, K)) # This code is contributed by ksam24000 |
C#
// C# code to implement the approach using System; public class GFG { // Function to find the maximum money thief can rob static int maximizeMoney( int N, int K) { if ((N & 1) != 0) { return (N + 1) * K / 2; } else { return N * K / 2; } } static public void Main() { int N = 5, K = 10; // Function call Console.WriteLine(maximizeMoney(N, K)); } } // This code is contributed by Rohit Pradhan |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum // money thief can rob function maximizeMoney(N, K) { if (N & 1) return (N + 1) * K / 2; else return N * K / 2; } // Driver Code let N = 5, K = 10; // Function Call document.write(maximizeMoney(N, K)); // This code is contributed by Potta Lokesh </script> |
Output
30
Time Complexity: O(1)
Auxiliary Space: O(1)