spek's blog

Hackerrank problem help
By spek, 3 years ago, In English

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:

  1. created a map<weights, count>
  2. 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)
  3. 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;
}
  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Check this test case:

3

1 2 1

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh man did not realise this. thank you.

    btw lets say I do this

    approach 1, do points 2 then 3
    approach 2, do points 3 then 2

    get the max of approach 1 and 2 as the answer

    will this be sufficient? i do not have access to the question or the testcases anymore so I cannot cross check

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It should be sufficient to do the approaches at once, i.e. iterate over weights, and for each

      1. take $$$freq_i // 2$$$, do $$$freq_i -= 2*freq_i//2$$$.

      2. If you have one left over, and $$$freq_{i+1} > 0$$$, add 1 to answer and subtract 1 from $$$freq_{i+1}$$$.

      The reason is that when you're doing approach 1, and are left with a single weight, the only thing you can do is combine it with the 1 higher. You never lose out by doing so, because in the worst case you make 1 pair ($$$i$$$,$$$i+1$$$) and because you used up $$$i+1$$$, you will make 1 fewer pair later (either because you'll now have a leftover $$$i+1$$$ which could've been paired up with it, or whenever later on). But by not trying it, you might lose out (like in the 1 2 1 case).

      → Reply