Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Beautiful Quadruples Problem Solution

HackerRank Beautiful Quadruples Problem Solution

Posted on May 10, 2023May 10, 2023 By Yashwant Parihar No Comments on HackerRank Beautiful Quadruples Problem Solution

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

Table of Contents

  • Beautiful Quadruples C Solution
  • Beautiful Quadruples C++ Solution
  • Beautiful Quadruples C Sharp Solution
  • Beautiful Quadruples Java Solution
  • Beautiful Quadruples JavaScript Solution
  • Beautiful Quadruples Python 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 Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Gena Playing Hanoi Problem Solution
Next Post: HackerRank Red Knight’s Shortest Path Solution

Related Posts

HackerRank Caesar Cipher Problem Solution HackerRank Caesar Cipher Problem Solution c
HackerRank Jumping Rooks Problem Solution HackerRank Jumping Rooks Problem Solution c
HackerRank Gridland Metro Problem Solution HackerRank Gridland Metro Problem Solution c
HackerRank Manasa and Stones Problem Solution HackerRank Manasa and Stones Problem Solution c
HackerRank Save the Prisoner! Problem Solution HackerRank Save the Prisoner! Problem Solution c
HackerRank Extra Long Factorials Problem Solution HackerRank Extra Long Factorials Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme