Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Výsledok je matematický trik.
Spočítaj počet núl, ktoré sa nachádzajú v binárom čísle n a výsledok je mocnina 2 s exponentom, ktorý má hodnotu počtu núl.
Keď sa pozrieme na pravdivostnú tabuľku operácie XOR:
|
1 2 3 4 |
0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 |
Potom sa pozrieme na pravdivostnú tabuľku sčítania v dvojkovej sústave:
|
1 2 3 4 |
0 + 0 = 0 (presun do vyššieho rádu 0) 0 + 1 = 1 (presun do vyššieho rádu 0) 1 + 0 = 1 (presun do vyššieho rádu 0) 1 + 1 = 0 (presun do vyššieho rádu 1) (=10) |
To znamená, že ščítanie dvoch binárnych číslic je XOR dvoch binárnych číslic. Do vyššieho rádu sa prenáša len pri operácii AND dvoch binárnych číslic.
Ak sa pozrieme na 2 operandy A a B, kde A ^ B = A + B. My potrebujeme vedieť prípady, keď nenastáva posun 1 do vyššieho rádu. Ten nastane iba vtedy, ak sú i-tý bit v A a i-tý bit v B rovný 1. Ak je nejaký bit v A rovný nula, vtedy môže byť bit na rovnakom indexe v B rovný hocičomu.
Vytvoril som riešenie v týchto programovacích jazykoch:
Všetky riešenia sú dostupné aj na mojom GitHub profile.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; public class Solution { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); long n = stdin.nextLong(); String binary = Long.toBinaryString(n); long zeroes = 0L; for(int i = 0; i < binary.length(); i++) { if(binary.charAt(i) == '0') { zeroes++; } } if(n == 0L) { zeroes = 0; } long result = (long) Math.pow(2, zeroes); System.out.println(result); stdin.close(); } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
'use strict'; const processData = input => { const num = parseInt(input); const binary = num.toString(2); let zeroes = 0; for(let i = 0; i < binary.length; i++) { if(binary[i] === '0') { zeroes++; } } if(num === 0) { zeroes = 0; } const result = Math.pow(2, zeroes); console.log(result); }; process.stdin.resume(); process.stdin.setEncoding("ascii"); let _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |
Scala
|
1 2 3 4 5 6 7 8 9 |
object SumVsXor extends App { val n = Source.stdin.bufferedReader().readLine().toLong val satisfied = Math.pow(2L, if(n == 0L) 0 else n.toBinaryString.count(_ == '0')).toLong println(satisfied) } |
Ruby
|
1 2 3 4 5 6 7 |
n = gets.strip.to_i binary = n.to_s(2) zeroes = binary.count("0") zeroes = 0 if n == 0 result = 2**zeroes puts result |