We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Game of Stones
  5. Discussions

Game of Stones

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 157 Discussions, By:

votes

Please Login in order to post a comment

  • kevindu
    6 years ago+ 11 comments

    This is the O(1) solution based on the pattern.

    for _ in xrange(input()):
         print ["First","Second"][input()%7 in [0,1]]
    
    63|
    Permalink
    View more Comments..
  • jpritcha3_14
    5 years ago+ 1 comment

    The pattern emerges pretty quickly if you start from 1 stone and look at if the first player will win or lose with each stone you add.

    SPOILER

    You'll find that the first player will lose when the starting number of stones s is: 1,7,8,14,15,21,22... (i.e. when s % 7 < 2). With this knowledge in hand the code is trivial:

    t = int(raw_input())
    for _ in xrange(t):
        s = int(raw_input())
        if s % 7 < 2:
            print 'Second'
        else:
            print 'First'
    
    32|
    Permalink
  • NAklecha
    6 years ago+ 1 comment

    Guys try it yourself for like 20 cases, on a paper! You will find out :P

    19|
    Permalink
  • tao_zhang
    6 years ago+ 1 comment

    This game is composed of the repeating group of LWWWWWL Therefore the solution in Java is like this --> System.out.println(scanner.nextInt()%7<2?"Second":"First");

    Source: https://www.cs.umd.edu/~gasarch/COURSES/250/S15/nimnotes.pdf

    7|
    Permalink
  • reinaldo_rafael1
    5 years ago+ 1 comment

    C++ Solution and Explaination:

    At first I had tried to modulos N by 10 (n = n%10) and set the number of if statements for each possibility from 1 to 10 to determine the winner, I was completely wrong. So I purchased the Test Cases for TC #0 and noticed that the pattern repeated itself after the 7th entry, it would go "Second First First First First First Second" and after that the pattern was the same. So I realized the best answer was to check if n was equal or greater than 7 and if so modulus n by 7 (n = n % 7). If the remainder was 0, it meant n was equal to the 7th case of the pattern (7 or 14 for example) and Player 2 Wins or if the reminder was 1, it meant n was equal to the 1st case of the pattern (8 or 15 for example) and Player 2 wins, any other remainder meant Player 1 wins.

    int main() {
        int t;
        cin >> t;
        
        for(int i = 0; i < t; i++){
            int n;
            cin >> n;
            
            if(n >= 7)
                n %= 7;
            
            if(n == 0 || n == 1)
                cout << "Second" <<  endl;
            else
                cout << "First" << endl;
            
        }
        return 0;
    }
    
    6|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature