Falling Euro coins

TalentHub News

[Coding Challenge Tips] Heads I Win, Tails You Lose

To help your job search along, try participating in the TalentHub Coding Challenges. It’s a great addition to your resume and the perfect way to show off your coding skills to companies hiring programmers in Japan.

Go try one right now, or keep reading for tips on how to complete on of the previous challenges below!

Heads I Win, Tails You Lose

Difficulty: ★★★☆☆

Problem statement

The rivalry between Michael and Ray seems endless. These two boys even compete with each other by coin flipping.
Just now, Michael suggested a game with the following rules:
“Each person will flip a separate coin. If it lands on heads, the person who flipped the coin gets 1 point, otherwise no point is granted. After n flips, the person who has more points wins.”
Being fed up with such childish competition between his two friends, David comes to you in a need for support so that he can code the probability of Michael winning over Ray.

Input
– Enter n denoting the number of flips.

Output
– Print the number of cases where Michael wins over Ray mod 10^9+7, as the number can be very large.

Constraints:
– n <= 20

Sample Input
2

Sample Output
5

Answer

Suppose the number of times that one player has k point is cnt[k].
Then the result will be: sum of (cnt[k] * sum of (cnt[i]) with i < k).
We can use bitmask to compute cnt[k].

Here is sample code.

#include <iostream>
#include <string.h>
using namespace std;
#define MOD 1000000007
const int N = 21;
int n;
unsigned long long cnt[N];
int main(){
ios_base::sync_with_stdio(false);
cin >> n;
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < (1 << n); ++i) {
cnt[__builtin_popcount(i)]++;
}
int sum = 0, ans = 0;
for(int i = 0; i <= n; ++i){
ans = (ans + sum * cnt[i]) % MOD;
sum = (sum + cnt[i]) % MOD;
}
cout << ans << endl;
return 0;
}

 

The origin of otoshidama, Japan New Year giftWhat is the origin of “Otoshidama”?Prev

Do you know about “Oomisoka” (New Year’s Eve)?NextOomisoka fireworks New Year in Japan

Related post

  1. TalentHub News

    [1/17]Challenge has been updated!!

    Hi!Just added new Challenges fo…

  2. Author: M.Kok

    Tech Trends to Watch for in 2021

    It is not easy to predict job marke…

  3. TalentHub News

    [7/18]New Challenges have been updated!

    Hey everyone!I’m TalentHub stuf…

  4. TalentHub News

    [6/8] 3 NEW challenges have been updated!!!

    Hi,Join our coding challenge co…

  5. TalentHub News

    [2/7] Compete with High Level Programmers!

    Prove how good you are at our new C…

  1. Author: M.Kok

    Shinnenkai – New year party in Jap…
  2. Japanese for Work Videos

    Explain Your Dreams and Goals – Vi…
  3. TalentHub News

    [12/26] Want to Win Cash Prize in Our Br…
  4. TalentHub News

    6/1 NEW JOB: Assistant manager for Site …
  5. Interviews

    Interview: Game designer Tarek talks abo…
PAGE TOP