HackerRank ‘Counter Game’ Solution

Short Problem Definition:

Louise and Richard play a game. They have a counter set to N. Louise gets the first turn and the turns alternate thereafter. In the game, they perform the following operations.

  • If N is not a power of 2, reduce the counter by the largest power of 2 less than N.
  • If N is a power of 2, reduce the counter by half of N.
  • The resultant value is the new N which is again used for subsequent operations.

The game ends when the counter reduces to 1, i.e., N == 1, and the last person to make a valid move wins.

Given N, your task is to find the winner of the game.


Counter Game


time complexity is O(N)

space complexity is O(1)


I really enjoyed this one. It can be solved without any while loops as long as you are aware of the input size. You get the previous power of two by computing the next one and shifting right. I consider it funny that this simple solution is not mentioned in the editorial.


def getClosestSmaller(x):
    x |= x >> 1
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    x = x + 1
    x = x >> 1
    return x

def getNrReductions(x):
    reductions = 1

    while (x != 1):
        #print x
        if x & (x - 1):
            #print "x is not power of two"
            x -= getClosestSmaller(x)
            #print "x is power of two"
            x /= 2
        reductions += 1    

    return reductions

if __name__ == '__main__':
    t = input()
    for _ in xrange(t):
        n = input()
        if getNrReductions(n) % 2 != 0:
            print "Richard"
            print "Louise"

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.


HackerRank ‘Insertion Sort Advanced Analysis’ Solution

Short Problem Definition:

Insertion Sort is a simple sorting technique which was covered in previous challenges. Sometimes, arrays may be too large for us to wait around for insertion sort to finish. Is there some other way we can calculate the number of times Insertion Sort shifts each elements when sorting an array?

If ki is the number of elements over which the ith element of the array has to shift, then the total number of shifts will be k1 +k2 +…+kN.


Insertion Sort Advanced Analysis


time complexity is O(N*log(N))

space complexity is O(1)


There are more solutions with nlogn time for this challenge. I decided to use Binary Indexed Trees as they are a data structure I am not that familiar with. The other solution includes a modified merge-sort that is posted as the problem editorial. BITs are effective for computing cumulative frequencies in log(N) time and are therefore perfectly suited for this problem. They assume a full tree and therefore are bound to the maximal range defined in the problem specification.

EDIT 2020: The solution no longer works. I added a new solution below that is based on Codility “ArrayInversionCount” Solution


class BinaryIndexedTree():
    def __init__(self, sz):
        self.sz = sz
        self.tree = [0] * sz

    def update(self, idx, val):
        while (idx <= self.sz):
               self.tree[idx] += val
               idx += (idx & -idx)
    def read(self, idx):
        sum = 0
        while (idx > 0):
            sum += self.tree[idx]
            idx -= (idx & -idx)
        return sum

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
     arr = map(int, raw_input().split())

        cnt = 0
        bit = BinaryIndexedTree(10**7+1)
        for val in reversed(arr):
            bit.update(val, 1)
            cnt += bit.read(val-1)
        print cnt

import math
import os
import random
import re
import sys

def mergeSort(alist):
    inversion_count = 0

    n = len(alist)
    if n == 1:
        return 0

    mid = len(alist) // 2
    lefthalf = alist[:mid]
    righthalf = alist[mid:]

    n1 = len(lefthalf)
    n2 = len(righthalf)

    inversion_count += mergeSort(lefthalf)
    inversion_count += mergeSort(righthalf)

    i = 0
    j = 0
    k = 0
    while i < n1 and j < n2:
        if lefthalf[i] <= righthalf[j]:
            alist[k] = lefthalf[i]
            i = i + 1
            alist[k] = righthalf[j]
            j = j + 1
            inversion_count += n1 - i
        k = k + 1

    while i < n1:
        alist[k] = lefthalf[i]
        i = i + 1
        k = k + 1

    while j < n2:
        alist[k] = righthalf[j]
        j = j + 1
        k = k + 1

    return inversion_count

if __name__ == '__main__':

    t = int(raw_input())

    for t_itr in xrange(t):
        n = int(raw_input())

        arr = map(int, raw_input().rstrip().split())

        result = mergeSort(arr)

        print result

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.