HackerRank Beautiful Quadruples Problem Solution

HackerRank Beautiful Quadruples Problem Solution

Yashwant Parihar,

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

11

Explanation
There are 11 beautiful quadruples for this input:

  1. (1, 1, 1, 2)
  2. (1, 1, 1, 3)
  3. (1, 1, 1, 4)
  4. (1, 1, 2, 3)
  5. (1, 1, 2, 4)
  6. (1, 1, 3, 4)
  7. (1,2,2,2)
  8. (1, 2, 2, 3)
  9. (1, 2, 2, 4)
  10. (1, 2, 3, 3)
  11. (1, 2, 3, 4)

Thus, we print 11 as our output.
Note that (1, 1, 1, 2) is same as (1, 1, 2, 1).

HackerRank Beautiful Quadruples Problem Solution
HackerRank Beautiful Quadruples Problem Solution

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()
c C# C++ HackerRank Solutions java javascript python

Leave a Reply