This content originally appeared on DEV Community and was authored by Ramiro Ocampo Rodriguez
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(' '));
});
}
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
This content originally appeared on DEV Community and was authored by Ramiro Ocampo Rodriguez
Ramiro Ocampo Rodriguez | Sciencx (2024-07-05T23:05:52+00:00) HackerRank Beautiful 3 Set Problem Solution. Retrieved from https://www.scien.cx/2024/07/05/hackerrank-beautiful-3-set-problem-solution/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.