In this post, we will solve HackerRank Beautiful Quadruples Problem Solution.
We call an quadruple of positive integers, (W, X, Y, Z), beautiful if the following
condition is true:
W X Y Z =/ 0
Note: is the bitwise XOR operator.
Given A, B, C, and D, count the number of beautiful quadruples of the form (W, X, Y, Z) where the following constraints hold:
When you count the number of beautiful quadruples, you should consider two quadruples as same if the following are true:
- They contain same integers.
- Number of times each integers occur in the quadruple is same.
For example (1, 1, 1, 2) and (1, 1, 2, 1) should be considered as same.
Input Format
A single line with four space-separated integers describing the respective values of A. B. C.
and D.
Output Format
Print the number of beautiful quadruples.
Sample Input
1 2 3 4
Sample Output
11Explanation
There are 11 beautiful quadruples for this input:
- (1, 1, 1, 2)
- (1, 1, 1, 3)
- (1, 1, 1, 4)
- (1, 1, 2, 3)
- (1, 1, 2, 4)
- (1, 1, 3, 4)
- (1,2,2,2)
- (1, 2, 2, 3)
- (1, 2, 2, 4)
- (1, 2, 3, 3)
- (1, 2, 3, 4)
Thus, we print 11 as our output.
Note that (1, 1, 1, 2) is same as (1, 1, 2, 1).
Beautiful Quadruples C Solution
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int A;
int B;
int C;
int D;
long long int d[4097][3002][5];
long long int dp(int x,int i,int k){
if(k==0){
if(x!=0){
return 1;
}
return 0;
}
int p=0;
if(i<=A) p++;
if(i<=B) p++;
if(i<=C) p++;
if(i<=D) p++;
if(p==0) return 0;
int j=0;
if(p<k) return 0;
long long int l=0;
for(j=0;j<=k;j++){
if(d[x][i+1][k-j]==-1){
d[x][i+1][k-j] = dp(x, i+1, k-j);
}
l+=d[x][i+1][k-j];
x=x^i;
}
return l;
}
int main(){
memset(d, -1, sizeof(d));
scanf("%d %d %d %d",&A,&B,&C,&D);
printf("%lld\n",dp(0, 1, 4));
return 0;
}
Beautiful Quadruples C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
typedef long long LL;
const int MAXV = 3e3 + 10;
const int MAXS = 1 << 12;
LL s[MAXV][MAXS], t[MAXV][MAXS];
LL _t[MAXV];
int main() {
int A, B, C, D;
cin >> A >> B >> C >> D;
int a[4];
a[0] = A;
a[1] = B;
a[2] = C;
a[3] = D;
sort(a, a + 4);
A = a[0];
B = a[1];
C = a[2];
D = a[3];
memset(s, 0, sizeof(s));
memset(t, 0, sizeof(t));
for (int i = 1; i <= A; ++i) {
for (int j = i; j <= B; ++j) {
s[j][i ^ j]++;
}
}
int all = 1 << 12;
for (int i = 1; i <= C; ++i) {
for (int j = 0; j < all; ++j) {
s[i][j] += s[i - 1][j];
}
}
for (int i = 1; i <= C; ++i) {
for (int j = i; j <= D; ++j) {
t[i][i ^ j]++;
}
}
for (int i = 1; i <= C; ++i) {
for (int j = 0; j < all; ++j) {
_t[i] += t[i][j];
}
}
LL ans = 0;
for (int i = 0; i < all; ++i) {
for (int j = 1; j <= C; ++j) {
if (s[j][i] && _t[j] != t[j][i]) {
ans += s[j][i] * (_t[j] - t[j][i]);
}
}
}
cout << ans << endl;
return 0;
}
Beautiful Quadruples C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
/*
* Complete the beautifulQuadruples function below.
*/
static Int64[] F = new Int64[3001];
static Int64 beautifulQuadruples(Int32 a, Int32 b, Int32 c, Int32 d) {
/*
* Write your code here.
*/
Int32[] arr = new Int32[4] {a,b,c,d};
Array.Sort(arr);
a = arr[0];
b = arr[1];
c = arr[2];
d = arr[3];
Int64[,] SB = new Int64[b + 1, 2];
SB[1, 0] = d * c - F[c - 1];
SB[1, 1] = SB[1, 0];
for (int i = 2; i <= b; i++)
{
SB[i, 0] = d * c - F[c - 1] - (d * (i - 1) - F[i - 2]);
SB[i, 1] = SB[i-1, 1] + SB[i, 0];
}
Int64[,] SA = new Int64[a + 1, 2];
SA[1,0] = SB[b,1];
SA[1,1] = SB[b, 1];
for (int i = 2; i <= a; i++)
{
SA[i, 0] = SA[i - 1, 0] - SB[i-1, 0];
SA[i, 1] = SA[i - 1, 1] + SA[i, 0];
}
Int64 Nulls = a * c - F[a - 1];
Int64 result = SA[a, 1] - Nulls;
Int32 MaxXor = (1 << (int)(Math.Log(d, 2) + 1)) - 1;
Int64[,] counts1 = new Int64[MaxXor + 1, b+1];
for (int i = 1; i <= a; i++)
{
for (int j = i+1; j <= b; j++)
{
counts1[i ^ j, j]++;
}
}
Int64[,] counts2 = new Int64[MaxXor + 1, c + 1];
for (int i = 1; i <= c; i++)
{
for (int j = i + 1; j <= d; j++)
{
counts2[i ^ j, i]++;
}
}
for (int i = 1; i <= MaxXor; i++)
{
for (int j = c; j >= 1; j--)
{
counts2[i, j-1] += counts2[i, j];
}
}
for (int i = 1; i <= MaxXor; i++)
{
for (int j = 1; j <= b; j++) {
checked{
result -= counts2[i, j] * counts1[i, j];}
}
}
return result;
}
static void Main(string[] args) {
F[0] = 0;
for (int i = 1; i <= 3000; i++)
{
F[i] = F[i - 1] + i;
}
TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);
string[] abcd = Console.ReadLine().Split(' ');
Int32 a = Convert.ToInt32(abcd[0]);
Int32 b = Convert.ToInt32(abcd[1]);
Int32 c = Convert.ToInt32(abcd[2]);
Int32 d = Convert.ToInt32(abcd[3]);
Int64 result = beautifulQuadruples(a, b, c, d);
textWriter.WriteLine(result);
textWriter.Flush();
textWriter.Close();
}
}Beautiful Quadruples Java Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int A = in.nextInt();
int B = in.nextInt();
int C = in.nextInt();
int D = in.nextInt();
int[] m = new int[] {A, B, C, D};
Arrays.sort(m);
long[][] count = new long[3001][4096];
for (int i=1; i<=m[0]; i++) {
for (int j=i; j<=m[1]; j++) {
count[j][i ^ j] ++;
}
}
for (int i=0; i<4096; i++) {
for (int j=1; j<=3000; j++) {
count[j][i] += count[j-1][i];
}
}
long[] sum = new long[3001];
for (int j=1; j<=3000; j++) {
for (int i=0; i<4096; i++) {
sum[j] += count[j][i];
}
}
long res=0;
for (int i=1; i<=m[2]; i++) {
for (int j=i; j<=m[3]; j++) {
int x = i ^ j;
res += sum[i] - count[i][i^j];
}
}
System.out.println(res);
}
}Beautiful Quadruples JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.trim().split('\n').map(str => str.trim());
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the beautifulQuadruples function below.
*/
function beautifulQuadruples(a, b, c, d) {
[a, b, c, d] = [a,b,c,d].sort((a, b) => a - b)
let count = 0
let cache = {}
// w x y z
for (let w = 1; w <= a; w++) {
for (let x = w; x <= b; x++) {
const key = w ^ x;
if (cache[key] && cache[key][x] != undefined){
count += cache[key][x]
continue
}
cache[key] = new Array(c + 1)
for (let y = c; y >=x; y--) {
let value = w ^ x ^ y;
let exists = value >= y && value <= d ? 1 : 0
let number = (d - y + 1) - exists
cache[key][y] = (cache[key][y + 1] || 0) + number
count += number
}
}
}
return count
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const abcd = readLine().split(' ');
const a = parseInt(abcd[0], 10);
const b = parseInt(abcd[1], 10);
const c = parseInt(abcd[2], 10);
const d = parseInt(abcd[3], 10);
let result = beautifulQuadruples(a, b, c, d);
ws.write(result + "\n");
ws.end();
}Beautiful Quadruples Python Solution
#!/bin/python3
import os
import sys
#
# Complete the beautifulQuadruples function below.
#
def beautifulQuadruples(a, b, c, d):
#
# Write your code here.
#
arr=[a,b,c,d]
arr.sort()
A=arr[0]
B=arr[1]
C=arr[2]
D=arr[3]
ans=0
total=[0]*3001
for i in range(1,A+1):
for j in range(i,B+1):
total[j]+=1
for i in range(1,3001):
total[i]+=total[i-1]
count=[[0 for i in range(4097)] for j in range(3001)]
print(count[0][0])
for i in range(1,A+1):
for j in range(i,B+1):
e=i^j
count[j][e]+=1
print(count[0][0])
for i in range(0,4097):
for j in range(1,3001):
count[j][i]+=count[j-1][i]
for i in range(1,C+1):
for j in range(i,D+1):
ans+=(total[i]-count[i][i^j])
return ans
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()
