Cerinta completa

Given a long integer , count the number of values of satisfying the following conditions:

where and are long integers and is the bitwise XOR operator.

You are given queries, and each query is in the form of a long integer denoting . For each query, print the total number of values of satisfying the conditions above on a new line.

For example, you are given the value . Condition requires that . The following tests are run:




We find that there are values meeting the first condition: and .

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 , the number of queries.
Each of the next lines contains a long integer describing the value of for a query.

Constraints

Subtasks

For of the maximum score:

Output Format

For each query, print the number of values of 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 queries:

  1. For the only value of satisfying is . This also satisfies our other condition, as and . Because we have one valid and there are no more values to check, we print on a new line.

  2. For , the following values of satisfy our conditions:





    There are five valid values of .

Sample Input 1

2
5
100

Sample Output 1

2
27

Explanation 1

In the first case:


In the second case, the first 10 values are:










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