|
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++
#include <bits/stdc++.h>
using namespace std;
int maximizeMoney(int N, int K)
{
if (N & 1)
return (N + 1) * K / 2;
else
return N * K / 2;
}
int main()
{
int N = 5, K = 10;
cout << maximizeMoney(N, K) << endl;
return 0;
}
|
Java
import java.io.*;
class GFG {
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;
System.out.println(maximizeMoney(N, K));
}
}
|
Python3
def maximizeMoney( N, K):
if (N & 1):
return (N + 1) * K / 2
else:
return N * K / 2
N = 5
K = 10
print(maximizeMoney(N, K))
|
C#
using System;
public class GFG {
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;
Console.WriteLine(maximizeMoney(N, K));
}
}
|
Javascript
<script>
function maximizeMoney(N, K) {
if (N & 1)
return (N + 1) * K / 2;
else
return N * K / 2;
}
let N = 5, K = 10;
document.write(maximizeMoney(N, K));
</script>
|
Time Complexity: O(1)
Auxiliary Space: O(1)
|
