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

  • Problemă: Manipulative Numbers

Cerinta completa

Suppose that [Expresie matematică indisponibilă în copia arhivată] is a list of [Expresie matematică indisponibilă în copia arhivată] numbers [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] is a permutation of these numbers, we say B is K-Manipulative if and only if:

[Expresie matematică indisponibilă în copia arhivată] is not less than [Expresie matematică indisponibilă în copia arhivată], where [Expresie matematică indisponibilă în copia arhivată] represents the XOR operator.

You are given [Expresie matematică indisponibilă în copia arhivată]. Find the largest [Expresie matematică indisponibilă în copia arhivată] such that there exists a K-manipulative permutation [Expresie matematică indisponibilă în copia arhivată].

Input:

The first line is an integer [Expresie matematică indisponibilă în copia arhivată]. The second line contains [Expresie matematică indisponibilă în copia arhivată] space separated integers – [Expresie matematică indisponibilă în copia arhivată].

Output:
The largest possible [Expresie matematică indisponibilă în copia arhivată], or [Expresie matematică indisponibilă în copia arhivată] if there is no solution.

Constraints:

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

Sample Input 0

3
13 3 10

Sample Output 0

2

Explanation 0

Here the list [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată]. One possible permutation [Expresie matematică indisponibilă în copia arhivată]. Here [Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată].
So there exists a permutation [Expresie matematică indisponibilă în copia arhivată] of [Expresie matematică indisponibilă în copia arhivată] such that [Expresie matematică indisponibilă în copia arhivată] is not less than [Expresie matematică indisponibilă în copia arhivată]. However there does not exist any permutation [Expresie matematică indisponibilă în copia arhivată] of [Expresie matematică indisponibilă în copia arhivată] such that [Expresie matematică indisponibilă în copia arhivată] is not less than [Expresie matematică indisponibilă în copia arhivată]. So the maximum possible value of [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată].

Sample Input 1

4
1 2 3 4

Sample Output 1

1

Explanation 1

Here the list [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată]. One possible permutation [Expresie matematică indisponibilă în copia arhivată]. Here [Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată].
So there exists a permutation [Expresie matematică indisponibilă în copia arhivată] of [Expresie matematică indisponibilă în copia arhivată] such that [Expresie matematică indisponibilă în copia arhivată] is not less than [Expresie matematică indisponibilă în copia arhivată]. However there does not exist any permutation [Expresie matematică indisponibilă în copia arhivată] of [Expresie matematică indisponibilă în copia arhivată] such that [Expresie matematică indisponibilă în copia arhivată] is not less than [Expresie matematică indisponibilă în copia arhivată]. So the maximum possible value of [Expresie matematică indisponibilă în copia arhivată] is [Expresie matematică indisponibilă în copia arhivată].

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