In this HackerRank Beautiful Quadruples problem solution, we have given the (W, X, Y, Z) quadruples of positive integers and if the bitwise XOR of all the quadruples is not equal to zero then we consider it as beautiful quadruples. so we need to count the number of beautiful quadruples. and remember that two quadruples are the same if they contain the same integers and the number of times each integer occurs in the quadruple is the same.
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the beautifulQuadruples function below.
#
def beautifulQuadruples(A, B, C, D):
A, B, C, D = sorted([int(A),int(B),int(C),int(D)])
total = [0] * (3010)
cnt = [[0 for j in range(4200)] for i in range(3010)]
for i in range(1,A+1):
for j in range(i,B+1):
total[j] += 1
cnt[j][i^j] += 1
for i in range(1,3001):
total[i] += total[i-1]
for j in range(4101):
cnt[i][j] += cnt[i-1][j]
res = 0
for i in range(1,C+1):
for j in range(i,D+1):
res += total[i] - cnt[i][i^j]
return(res)
#
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
abcd = input().split()
a = int(abcd[0])
b = int(abcd[1])
c = int(abcd[2])
d = int(abcd[3])
result = beautifulQuadruples(a, b, c, d)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
/*
* Complete the beautifulQuadruples function below.
*/
static Map<String, Boolean> memoiz = new HashMap();
static boolean isBeautiful(int a, int b, int c, int d) {
int [] arr = new int[4];
arr[0] = a;
arr[1] = b;
arr[2] = c;
arr[3] = d;
Arrays.sort(arr);
String keyStr = String.valueOf(arr[0]) + "_" +
String.valueOf(arr[1]) + "_" +
String.valueOf(arr[2]) + "_" +
String.valueOf(arr[3]);
if (memoiz.containsKey(keyStr)) {
return false;
}
memoiz.put(keyStr, true);
if ( (a ^ b ^ c ^ d) != 0 ) {
return true;
}
else
return false;
}
static long beautifulQuadruples(int a, int b, int c, int d) {
long count = 0;
Map<Integer, Integer> fHalf = new HashMap();
Map<Integer, Integer> sHalf = new HashMap();
int[] ar = new int[4];
ar[0] = a;
ar[1] = b;
ar[2] = c;
ar[3] = d;
Arrays.sort(ar);
long acc = 0;
for (int ai = 1; ai <= ar[2]; ai++) {
for (int bi = ai; bi <= ar[3]; bi++) {
int xor = ai ^ bi;
fHalf.put(xor, fHalf.getOrDefault(xor, 0) + 1);
acc += 1L;
}
}
for (int x = 1; x <= ar[1]; x++) {
for (int w = 1; w <= Math.min(ar[0], x); w++) {
int xor = w ^ x;
count += acc - fHalf.getOrDefault(xor, 0);
//fHalf.put(xor, fHalf.getOrDefault(xor, 0) + 1);
}
int y = x;
for (int z = x; z <= ar[3]; z++) {
int xor = y ^ z;
fHalf.put(xor, fHalf.getOrDefault(xor, 0) - 1);
acc -= 1L;
}
}
return count;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] abcd = scanner.nextLine().split(" ");
int a = Integer.parseInt(abcd[0].trim());
int b = Integer.parseInt(abcd[1].trim());
int c = Integer.parseInt(abcd[2].trim());
int d = Integer.parseInt(abcd[3].trim());
long result = beautifulQuadruples(a, b, c, d);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedWriter.close();
}
}
Problem solution in C++.
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <utility>
#include <numeric>
#include <fstream>
using namespace std;
#define ALL(c) (c).begin(),(c).end()
#define SZ(c) int((c).size())
#define LEN(s) int((s).length())
#define FOR(i,n) for(int i=0;i<(n);++i)
#define FORD(i,a,b) for(int i=(a);i<=(b);++i)
#define FORR(i,a,b) for(int i=(b);i>=(a);--i)
typedef istringstream iss;
typedef ostringstream oss;
typedef long double ld;
typedef long long i64;
typedef pair<int,int> pii;
typedef vector<i64> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<string> vs;
int main()
{
//freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(0);
vector<int> A(4);
FOR(i, 4) cin >> A[i];
sort(ALL(A));
vi T(A[2]+1, 0);
vector<vector<int> > P(1<<12);
FORD(i, 1, A[0])
{
FORD(j, i, A[1])
{
T[j]++;
P[i^j].push_back(j);
}
}
FORD(i, 1, SZ(T)-1) T[i] += T[i-1];
FOR(i, SZ(P)) sort(ALL(P[i]));
i64 ans = 0;
FORD(i, 1, A[2])
{
FORD(j, i, A[3])
{
i64 tmp = T[i];
if (!P[i^j].empty())
tmp -= upper_bound(ALL(P[i^j]), i) - P[i^j].begin();
ans += tmp;
}
}
cout << ans << endl;
return 0;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define W 0
#define X 1
#define Y 2
#define Z 3
#define MAX 4096
char* readline();
char** split_string(char*);
void insert(int * arr, int count, int value) {
int i;
for (i = count - 1; i >= 0 && arr[i] > value; i--) {
arr[i + 1] = arr[i];
}
arr[i + 1] = value;
}
int min(int a, int b) {
return a < b ? a : b;
}
/*
* Complete the beautifulQuadruples function below.
*/
long beautifulQuadruples(int _w, int _x, int _y, int _z) {
/*
* Write your code here.
*/
int sortedInput[4];
unsigned long * count;
unsigned long numPairs = 0;
unsigned long numBeautiful = 0;
insert(sortedInput, 0, _w);
insert(sortedInput, 1, _x);
insert(sortedInput, 2, _y);
insert(sortedInput, 3, _z);
count = (unsigned long *)calloc(MAX, sizeof(unsigned long));
if (count == NULL) { return - 1; }
for (int y = 1; y <= sortedInput[Y]; y++) {
for (int z = y; z <= sortedInput[Z]; z++) {
count[y ^ z]++;
numPairs++;
}
}
for (int x = 1; x <= sortedInput[X]; x++) {
for (int w = 1; w <= min(x, sortedInput[W]); w++) {
numBeautiful += numPairs - count[x ^ w];
}
// remove pairs (x, z)
for (int z = x; z <= sortedInput[Z]; z++) {
count[x ^ z]--;
}
numPairs -= (sortedInput[Z] - x + 1);
}
return numBeautiful;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char** abcd = split_string(readline());
char* a_endptr;
char* a_str = abcd[0];
int a = strtol(a_str, &a_endptr, 10);
if (a_endptr == a_str || *a_endptr != '\0') { exit(EXIT_FAILURE); }
char* b_endptr;
char* b_str = abcd[1];
int b = strtol(b_str, &b_endptr, 10);
if (b_endptr == b_str || *b_endptr != '\0') { exit(EXIT_FAILURE); }
char* c_endptr;
char* c_str = abcd[2];
int c = strtol(c_str, &c_endptr, 10);
if (c_endptr == c_str || *c_endptr != '\0') { exit(EXIT_FAILURE); }
char* d_endptr;
char* d_str = abcd[3];
int d = strtol(d_str, &d_endptr, 10);
if (d_endptr == d_str || *d_endptr != '\0') { exit(EXIT_FAILURE); }
long result = beautifulQuadruples(a, b, c, d);
fprintf(fptr, "%ld\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
0 Comments