Soluție HackerRank pentru The Great XOR. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: The Great XOR

Cerinta completa

Given a long integer [Expresie matematică indisponibilă în copia arhivată], count the number of values of [Expresie matematică indisponibilă în copia arhivată] satisfying the following conditions:

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

where [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] are long integers and [Expresie matematică indisponibilă în copia arhivată] is the bitwise XOR operator.

You are given [Expresie matematică indisponibilă în copia arhivată] queries, and each query is in the form of a long integer denoting [Expresie matematică indisponibilă în copia arhivată]. For each query, print the total number of values of [Expresie matematică indisponibilă în copia arhivată] satisfying the conditions above on a new line.

For example, you are given the value [Expresie matematică indisponibilă în copia arhivată]. Condition [Expresie matematică indisponibilă în copia arhivată] requires that [Expresie matematică indisponibilă în copia arhivată]. The following tests are run:

[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]

We find that there are [Expresie matematică indisponibilă în copia arhivată] values meeting the first condition: [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

Function Description

Complete the theGreatXor function in the editor below. It should return an integer that represents the number of values satisfying the constraints.

theGreatXor has the following parameter(s):

  • x: an integer

Input Format

The first line contains an integer [Expresie matematică indisponibilă în copia arhivată], the number of queries.
Each of the next [Expresie matematică indisponibilă în copia arhivată] lines contains a long integer describing the value of [Expresie matematică indisponibilă în copia arhivată] for a query.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Subtasks

For [Expresie matematică indisponibilă în copia arhivată] of the maximum score:

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]

Output Format

For each query, print the number of values of [Expresie matematică indisponibilă în copia arhivată] satisfying the given conditions on a new line.

Sample Input 0

2
2
10

Sample Output 0

1
5

Explanation 0

We perform the following [Expresie matematică indisponibilă în copia arhivată] queries:

  1. For [Expresie matematică indisponibilă în copia arhivată] the only value of [Expresie matematică indisponibilă în copia arhivată] satisfying [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată]. This also satisfies our other condition, as [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]. Because we have one valid [Expresie matematică indisponibilă în copia arhivată] and there are no more values to check, we print [Expresie matematică indisponibilă în copia arhivată] on a new line.

  2. For [Expresie matematică indisponibilă în copia arhivată], the following values of [Expresie matematică indisponibilă în copia arhivată] satisfy our conditions:

    [Expresie matematică indisponibilă în copia arhivată]
    [Expresie matematică indisponibilă în copia arhivată]
    [Expresie matematică indisponibilă în copia arhivată]
    [Expresie matematică indisponibilă în copia arhivată]
    [Expresie matematică indisponibilă în copia arhivată]

    There are five valid values of [Expresie matematică indisponibilă în copia arhivată].

Sample Input 1

2
5
100

Sample Output 1

2
27

Explanation 1

In the first case:
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
In the second case, the first 10 values are:
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]

Limbajul de programare folosit: cpp14

Cod:

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

int visit(int ***A, int i, int j, int n, int m, int size) {
    (*A)[i][j] = -1;
    size++;
    if(i-1 >= 0 && j-1 >= 0 && (*A)[i-1][j-1] == 1) {
        size += visit(A, i-1, j-1, n, m, 0);
    }
    if(i-1 >= 0 && (*A)[i-1][j] == 1) {
        size += visit(A, i-1, j, n, m, 0);
    }
    if(i-1 >= 0 && j+1 < m && (*A)[i-1][j+1] == 1) {
        size += visit(A, i-1, j+1, n, m, 0);
    }
    if(j-1 >= 0 && (*A)[i][j-1] == 1) {
        size += visit(A, i, j-1, n, m, 0);
    }
    if(j+1 < m && (*A)[i][j+1] == 1) {
        size += visit(A, i, j+1, n, m, 0);
    }
    if(i+1 < n && j-1 >= 0 && (*A)[i+1][j-1] == 1) {
        size += visit(A, i+1, j-1, n, m, 0);
    }
    if(i+1 < n && (*A)[i+1][j] == 1) {
        size += visit(A, i+1, j, n, m, 0);
    }
    if(i+1 < n && j+1 < m && (*A)[i+1][j+1] == 1) {
        size += visit(A, i+1, j+1, n, m, 0);
    }
    return size;
}


int main(){
    long long q;
    cin >> q;
    for(long long a0 = 0; a0 < q; a0++){
        long long x;
        cin>>x;
        // Find the length of the binary representation of x
        long long length = 1;
        long long powerOf2 = 1;
        while(powerOf2 < x) {
        	powerOf2 *= 2;
        	length++;
        }
        // Iterate over x's binary representation, each time we hit a 1
        // we can immediately deduct from the total of satisfying #'s
        powerOf2 = 1;
        long long numSatisfying = x-1;
        for(long long i = 0; i < length; i++) {
        	if(x & powerOf2) {
        		numSatisfying -= min(powerOf2, x-powerOf2);
        	}
            powerOf2*=2;
        }
        cout<<numSatisfying<<"\n";
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464603533

Link challenge: https://www.hackerrank.com/challenges/the-great-xor/problem

The Great XOR