Today I have solved the problem in javascript

You are given a tree with an even number of nodes. Consider each connection between a parent and child node to be an "edge". You would like to remove some of these edges, such that the disconnected subtrees that remain each have an even number of nodes.


For example, suppose your input was the following tree:


   1

  / \ 

 2   3

    / \ 

   4   5

 / | \

6  7  8

In this case, removing the edge (3, 4) satisfies our requirement.


Write a function that returns the maximum number of edges you can remove while still satisfying this requirement.


 const tree = [

    [1],

    [0, 3],

    [5],

    [1, 4, 5],

    [3],

    [2, 3, 6, 7, 8],

    [5],

    [5],

    [5]

];


const result = maxEdgesToRemove(tree);

function maxEdgesToRemove(tree) {

    const dfs = (node, parent, evenCount) => {

        let edgesToRemove = 0;


        for (const child of tree[node]) {

            if (child !== parent) {

                edgesToRemove += dfs(child, node, evenCount);

            }

        }


        if (evenCount[node] % 2 !== 0) {

            evenCount[parent]++;

            edgesToRemove++;

        }


        return edgesToRemove;

    };


    const n = tree.length;

    const evenCount = new Array(n).fill(1); 


    return dfs(0, -1, evenCount);

}



console.log(result); 

Output:

8

Comments

Post a Comment

Popular posts from this blog

Building a Full-Stack Student Management System with React.js and NestJS

  🚀 My Journey Creating a Student Management System 🌟 I'm excited to share my recent project — a Student Management System ! This project gave me hands-on experience in building a full-stack application, enhancing both my frontend and backend development skills. 💡 Project Overview The Student Management System is designed to help educational institutions efficiently manage student data, including enrollment, attendance, and performance. The goal was to create a user-friendly platform for both students and administrators. 🔨 Tech Stack Used ✅ Frontend: JavaScript, HTML, CSS, React.js ✅ Backend: TypeScript, NestJS, Node.js ✅ Database: MongoDB (with _id for unique identifiers) 🌟 Key Features ✔️ Student Registration – Easy registration with unique ID management ✔️ Attendance Tracking – Real-time updates on student attendance ✔️ Performance Reports – Generate and view student performance reports ✔️ Admin Panel – Secure access for administrators to manage student...
Read more

Today I have solved the problem in javascript

 Consider the following scenario: there are N mice and N holes placed at integer points along a line. Given this, find a method that maps mice to holes such that the largest number of steps any mouse takes is minimized.Each move consists of moving one mouse one unit to the left or right, and only one mouse can fit inside each hole.For example, suppose the mice are positioned at [1, 4, 9, 15], and the holes are located at [10, -5, 0, 16]. In this case, the best pairing would require us to send the mouse at 1 to the hole at -5, so our function should return 6. const mice = [1, 4, 9, 15]; const holes = [10, -5, 0, 16]; function minSteps(mice, holes) {    mice.sort((a, b) => a - b);     holes.sort((a, b) => a - b); let maxSteps = 0;     for (let i = 0; i < mice.length; i++) {         let steps = Math.abs(mice[i] - holes[i]);         if (steps > maxSteps) {             maxStep...
Read more

Today I have solved problem in javascript

 You are given an array X of floating-point numbers x1, x2, ... xn. These can be rounded up or down to create a corresponding array Y of integers y1, y2, ... yn. Write an algorithm that finds an appropriate Y array with the following properties: The rounded sums of both arrays should be equal. The absolute pairwise difference between elements is minimized. In other words, |x1- y1| + |x2- y2| + ... + |xn- yn| should be as small as possible. For example, suppose your input is [1.3, 2.3, 4.4]. In this case you cannot do better than [1, 2, 5], which has an absolute difference of |1.3 - 1| + |2.3 - 2| + |4.4 - 5| = 1. const inputArray = [1.3, 2.3, 4.4]; const resultArray = roundArray(inputArray); function roundArray(inputArray) {     const n = inputArray.length;     const roundedArray = [];     let roundedSum = 0; for (let i = 0; i < n; i++) {         consat roundedValue = Math.round(inputArray[i]);         rounded...
Read more