Modular game of numbers - hackerrank

general
1

Please can someone explain the approach to this problem ?

Link - https://www.hackerrank.com/contests/101hack47/challenges/modular-game-of-numbers

Thanks!!

2

Yup, heres my code-

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    int p;
    int q;
    cin >> n >> p >> q;
    vector<int> a(p);
    for(int a_i = 0; a_i < p; a_i++){
       cin >> a[a_i];
    }
    vector<int> b(q);
    for(int b_i = 0; b_i < q; b_i++){
       cin >> b[b_i];
    }
    int i,j,sum;
    int ans[4001];
    for(i=0;i< 4001;i++)
        ans[i]=-1;
    for(i=0;i< p;i++)
        {
        for(j=0;j< q;j++)
            {
            sum=a[i]+b[j];
            int rem= sum%n;
            ans[n-rem]++;
                   }
    }
    int min=999999,numind=1;
    for(i=1;i<=n;i++)
        {
        //cout< < ans[i]< < " "< < "i is "<< i< < endl;
        if(ans[i]< min)
        {
            //cout<<"If executed"<< endl;
            min=ans[i];
            numind=i;
        }
    }
    cout<< numind<< endl;
    // Write Your Code Here
    return 0;
}

Basically what I did was to find sum of all possible combinations from list of her 2 friends, and hence add one to the counter (which counts the number of combination for which a number ‘i’ would make her lose). Then I print the one with minimum value of counter.

I think an example will do more justice.

Let the input be-

3 2 1
1 2
3

Now, n=3. The sums possible from given lsit are-

  • 1+3=4
  • 2+3=5

Now first I mod them with n. (Since it can be proved that taking a number greater than n is ineffective. Eg- If the sum is 4, and I choose 2, then its no use. Similarly if all numbers of form 5,8 …2+3*(k) [k is an integer] will give remainder 2 and make her lose the game. Think on this, this is a tricky part. Number greater than n are to be ignored.)

So I mod the number and get remainder.

Now I make an array arr[n+1] which counts that for how many combinations will the number ‘i’ make her lose.

4%3=1
==> arr[3-1]++; (Since if she chooses 3-1=2, she would lose!)

5%3=2
==>arr[3-2]++

Note that arr[0] is still 0, and that’s the minimum. But 0 isn’t an option she could choose. Effectively, a remainder of 0 from side of Alice means she choose a multiple of n. And going by the constraints of printing smallest integer, we print n itself.

Basic idea-

  • Acknowledge that its all playing with remainders. Numbers greater than n are ineffective and are to be ignored in interest that if number K is giving least probability, then K%N will also give same probability (She loses if (Sums of Her friends number)% N + Her Number%N =0, meaning if the number is such that its remainder +remainder of sum of numbers of her friends=N.
    ==> Remainder = N - (remainder-of-Sum-of-numbers-choosen-by-her-friends)

This is the remainder which would make her lose. We store how many combinations give this remainder. We repeat it for all combinations, storing how many losses does each remainder give. Then we print the one giving minimal loss)

1 Like
3

Yup i did the same and got 3 WAs…basically i found the min number such that the probability of her loosing the game becomes Zero! Is there anything wrong with our approach!

4

Its not necessary that probability is 0.

Eg- Take example of list being-

1 2 3 4

1

And n=3.

The sums are 2,3,4,5 i.e. rem = 0,1,2 all are possible. Here if you try to look for a number such that the probability is 0, then you wont find any.

5

yeah! Missed this.

6

Happens to even the best of us :slight_smile: