Cerinta completa

Suppose that is a list of numbers and is a permutation of these numbers, we say B is K-Manipulative if and only if:

is not less than , where represents the XOR operator.

You are given . Find the largest such that there exists a K-manipulative permutation .

Input:

The first line is an integer . The second line contains space separated integers – .

Output:
The largest possible , or if there is no solution.

Constraints:

Sample Input 0

3
13 3 10

Sample Output 0

2

Explanation 0

Here the list is . One possible permutation . Here
.
So there exists a permutation of such that is not less than . However there does not exist any permutation of such that is not less than . So the maximum possible value of is .

Sample Input 1

4
1 2 3 4

Sample Output 1

1

Explanation 1

Here the list is . One possible permutation . Here
.
So there exists a permutation of such that is not less than . However there does not exist any permutation of such that is not less than . So the maximum possible value of is .

Limbajul de programare folosit: cpp14

Cod:

// https://www.hackerrank.com/challenges/manipulative-numbers

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

unsigned a[111111], b[111111];
int n;

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 31; i >= 0; i--) {
        for (int j = 0; j < n; j++)
            b[j] = a[j] >> i;

        sort(b, b + n);
        unsigned x = b[0];
        int cnt = 1, maxcnt = 1;

        for (int j = 1; j < n; j++) {
            if (b[j] == x) {
                ++cnt;
                if (cnt > maxcnt) maxcnt = cnt;
            } else {
                cnt = 1;
                x = b[j];
            }
        }

        if (maxcnt <= n - maxcnt) {
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

Scor obtinut: 1.0

Submission ID: 464612971

Link challenge: https://www.hackerrank.com/challenges/manipulative-numbers/problem

Manipulative Numbers