HackerRank Tower Breakers Revisited! problem solution

In this HackerRank Tower Breakers, Revisited! problem solution Two players (numbered 1 and 2) are playing a game of Tower Breakers! The rules of the game are as follows:

• Player 1 always moves first, and both players always move optimally.
• Initially there are N towers of various heights.
• The players move in alternating turns. In each turn, a player can choose a tower of height X and reduce its height to Y, where 1 <= Y < X and Y evenly divides X.
• If the current player is unable to make any move, they lose the game.

Given the value of N and the respective height values for all towers, can you determine who will win? If the first player wins, print 1; otherwise, print 2.

HackerRank Tower Breakers Revisited! problem solution in Python.

def divisors(m):
    c = 0
    while m % 2 == 0:
        c += 1
        m = m // 2

    for i in range(3, int(m**0.5) + 1, 2):
        while m % i == 0:
            c += 1
            m = m // i
    if m > 2:
        c += 1
    return c

def towers(n):
    global memo
    nim_sum = 0
    for i in sorted(n):
        if i == 1:
            continue
        else:
            if i not in memo:
                memo[i] = divisors(i)
            nim_sum ^= memo[i]
    return nim_sum

memo = {}
for _ in range(int(input())):
    n = input()
    print(2 if towers([int(x) for x in input().split()]) == 0 else 1)

Tower Breakers Revisited! problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-- > 0){
            int n = sc.nextInt();
            int q = 0;
            while(n-- > 0){
                int sum = getPrimeFactor(sc.nextInt(), 0);
                q = q^sum;
            }
            if(q==0){System.out.println("2");}
            else{System.out.println("1");}
        }
    }
    
    public static int getPrimeFactor(int num, int sum){
        while(num%2==0){
            sum = sum+1;
            num = num/2;
        }
        for(int i=3;i<=Math.sqrt(num); i=i+2){
            while(num%i==0){
                sum = sum +1;
                num = num/i;
            }
        }
        if(num>2)
            sum++;
        return sum;
    }
}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
using namespace std;

const int Maxm = 1000005;

int nim[Maxm];
set <int> S[Maxm];
int t;
int n;
int res;

int main() {
    for (int i = 1; i < Maxm; i++) {
        while (S[i].find(nim[i]) != S[i].end())
            nim[i]++;
        for (int j = i + i; j < Maxm; j += i)
            S[j].insert(nim[i]);
    }
    scanf("%d", &t);
    while (t--) {
        int res = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            int a; scanf("%d", &a);
            res ^= nim[a];
        }
        printf("%dn", res? 1: 2);
    }
    return 0;
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int countPrimeFactors(long long num, int sum);
int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int cases;
    scanf("%d",&cases);
    while(cases--){
        int towers,sum=0, xor=0;
        scanf("%d",&towers);
        long long heights[towers];
        int i;
        for(i=0;i<towers;i++){
            scanf("%lld",&heights[i]);
        }
        for(i=0;i<towers;i++){
            xor ^= countPrimeFactors(heights[i],sum);
        }
        if(xor==0){
            printf("2 n");
        }else{
            printf("1 n");
        }
    }
    return 0;
}

int countPrimeFactors(long long num, int sum){
    int i=0;
    while(num%2 ==0){
        num=num/2;
        sum += 1;
    }
    for(i=3;i<=sqrt(num);i+=2){
        while(num%i==0){
            num /=i;
            sum +=1;
        }
    }
    if(num>2){
        sum+=1;
    }
    return sum;
}