Important:
This problem is from my intermediate problem solving certificate on Hackerrank ( it is already over and I failed horribly).
I only managed to pass 3 out of 15 testcases and I am not sure where I went wrong, can someone help me?
Also, this is my first time posting so if there is anything I did wrongly please feel free to correct me, thank you.
Problem:
summarized version:
1. given an array of n elements containing the count of (i+1) dumbbell weights
2. find maximum pair of dumbbell weights whereby pairs can have difference of max 1
3. input are given as follows
n followed by n integers
4
2 4 3 1
arr = [2, 4, 3, 1] means
2x 1 kg dumbbell
4x 2 kg dumbbell
3x 3 kg dumbbell
1x 4 kg dumbbell
the answer will be 5 with the pairing as follows
[1kg, 1kg], [2kg, 2kg], [2kg, 2kg], [3kg, 3kg], [3kg, 4kg]
actual problem statement (sorry I did not manage to get the testcases)
My approach:
- created a map<weights, count>
- iterate over the map and find max pairs available for current weight
2.1. I find the max pair by taking floor of dividing the count by 2
2.2. then I add the max pair to my ans
2.3. reduce the count of current weight by (2 * max pair) - iterate over the map again (until second last element)
3.1 this time, I check if the count of (i > 0 and i+1 > 0)
3.2 I take min count of those 2 and add to my ans
3.3 then I reduce the count of i and i+1 by the min
a picture based on my approach:
My code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
map<ll, ll> hash;
for (ll i = 1; i <= n; i += 1) {
ll input;
cin >> input;
hash[i] = input;
}
ll ans = 0;
for (ll i = 1; i <= n; i += 1) {
ll temp = floor(hash[i] / 2.0);
ans += temp;
hash[i] = hash[i] - (2 * temp);
}
for (ll i = 1; i < n; i += 1) {
if ((hash[i] > 0) && (hash[i + 1] > 0)) {
ll temp = min(hash[i], hash[i + 1]);
ans += temp;
hash[i] -= temp;
hash[i + 1] -= temp;
}
}
cout << ans;
return 0;
}