DEV Community

Ramiro Ocampo Rodriguez
Ramiro Ocampo Rodriguez

Posted on

HackerRank Beautiful 3 Set Problem Solution

HackerRank Beautiful 3 Set Problem Solution

GitHub_ror2022

CV_ror2022

LinkedIn
portfolio

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(' '));
});
Enter fullscreen mode Exit fullscreen mode

}

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.

GitHub_ror2022

CV_ror2022

LinkedIn
portfolio

Top comments (0)