HackerRank Beautiful 3 Set Problem Solution

HackerRank Beautiful 3 Set Problem Solution

We will solve the HackerRank Beautiful 3 Set problem.

Given an integer nnn, a set SSS of triples (x,y,z)(x, y, z)(x,y,z) is beautiful if and only if:

0<=Xi,Yi,Zi

Xi + Yi + Zi = n

Let X be the set of different x's in S, Y be the set of different y's in S, and Z be the set of different z's in S. Then ∣X∣=∣Y∣=∣Z∣=∣S∣


The third condition means that all values of x, y, and z are pairwise distinct. Given n, find any beautiful set having the maximum number of elements. Then, print the cardinality of S (i.e., ∣S∣) on a new line, followed by ∣S∣ lines where each line contains 3 space-separated integers describing the respective values of x_i​, y_i​, and z_i.

Input Format

A single integer, n.

Output Format

On the first line, print the cardinality of S (i.e., ∣S∣).

For each of the ∣S∣ subsequent lines, print three space-separated numbers per line describing the respective values of x_i​, y_i​, and z_i​ for triple i in S.

Sample Input

3

Sample Output

3

0 1 2

2 0 1

1 2 0

Solution Analysis

We need a function in JavaScript that returns the combination of valid triples given a number n. This combination should satisfy:

Each of its triples (x,y,z) satisfies x+y+z=n.

The set of x values are distinct, the set of y values are distinct, and the set of z values are distinct.

The cardinality k is the length of the combination of triples that meets these conditions.

Examples Analysis

For n=1:

Cardinality: 1

Triples:

0 1 0

For n=2:

Cardinality: 2

Triples:

0 2 0

1 0 1

For n=3:

Cardinality: 3

Triples:

0 1 2

1 2 0

2 0 1

For n=4:

Cardinality: 3

Triples:

0 1 3

1 2 1

2 0 2

For n=5:

Cardinality: 4

Triples:

0 3 2

1 4 0

2 0 3

3 1 1

General Observations

From the examples, the pattern for the cardinality k can be observed as:

k=n−offset

where the offset follows the pattern 0,0,0,1,1,1,2,2,2,3,3,3,… so:

offset= Math.floor((n-1)/3)

The upper limit of z is k−1 and the lower limit is 0, unless n is part of the sequence 4,7,10,13,16,…where the upper limit becomes k and the lower limit becomes 1.

JavaScript Implementation

const beatiful3set= (data)=>{

//determ cardinality of the set based on the amount of elements

const n=Number(data); //amount of elements

const o=Math.floor((n-1)/3); //offset

const k=n-o; //cardinality of the set

//the cardinality of the set is the amount of triplets

// 0<=x<=k-1

//y=n-x-z



let evenZ=[];

let oddZ=[];



//first we need to determine if n is in the set 4,7,10,13,16,19,22,25,28,31,34,37,40,43,46,49,52,55.....

//create a function to determine if n is in the set

const isNInSet=(num)=>{

    let temp= (num-1)/3;

    if(Number.isInteger(temp) && temp>=1){

        return true;

    }else{

        return false;

    }

}

let upperLimZ=0;

let lowerLimZ=0;

if(isNInSet(n)===true){

    //if n is in the set then

    upperLimZ=k;

    lowerLimZ=1;

}else{

    //if n is not in the set then

    upperLimZ=k-1;

    lowerLimZ=0;

}











for(let c=upperLimZ;c>=lowerLimZ;c--){

    if(c%2===0){

        evenZ.push(c);

    }else{

        oddZ.push(c);

    }

}



//complete the set z 

let completeZ=[];

if(evenZ.length>=oddZ.length){

completeZ=[...evenZ,...oddZ];

}else{

completeZ=[...oddZ,...evenZ];

}



let triplets=[];

for(let x=0;x<k;x++){

        let z=completeZ[x];

        let y=n-x-z;

        triplets.push([x,y,z]);

    }

//output

console.log('Input n:',n);

console.log('cardinality:',k);

triplets.forEach(triplet=>{

    console.log(triplet.join(' '));

});

}

This function calculates the valid combination of triples for a given n and prints the cardinality and the triples themselves. The algorithm is designed to ensure that the conditions of the problem are met and provides a clear, efficient solution.