In this HackerRank Tower Breakers, Revisited! problem solution we have given the value of N towers and the respective height values for all towers. Do we need to determine who will win? if the first player wins, print 1 otherwise print 2.
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)
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; }