Make all even values inside loop equal in given Linked list
Given a linked list that contains integers, your task is to find the minimum cost for making all even numbers that are inside the cycle equal. You can perform the below-mentioned operations to achieve this :
- Increase a node’s value by 1, this will cost 1 operation.
- Decrease a node’s value by 1, this will cost 1 operation.
Examples :
Input: 1->2->4->6->2
Output: 6
Explanation: Even numbers inside a loop are 2, 4, 6, and 2. To make them equal, they need to be converted into 3.
- So, converting 2 -> 3 will cost 1 operation.
- converting 4->3 will cost 1 operation.
- converting 6->3 will cost 3 operations.
- converting 2->3 will cost 1 operation.
Minimum Cost = 1 + 1 + 3 + 1 = 6 operations.
Input: 1->2->3->4->8->12->NULL
Output: 0
Explanation: Since there is no loop in the given linked list, therefore, the cost will be 0.
Approach: To solve this problem, follow the below-mentioned instructions step by step:
- Start by detecting the loop in the linked list, if yes then proceed further otherwise directly return 0.
- If there exists a loop then iterate inside the loop track even numbers present inside the loop and store them in a vector.
- If the size of this vector is more than 1 (this shows that there are more than 1 even numbers so we need to make them equal) then pass this vector to findMinCost function otherwise return 0.
- In findMinCost, find average of all the elements in array, this average number is the number which every array element should be converted to.
- Then iterate over the array again and calculate the absolute difference between current element and average value, add this sum of all elements and then return it.
Below Code is the implementation of above approach in C++.
C++
// C++ program for the above mentioned approach #include <bits/stdc++.h> using namespace std; // Link list node class Node { public : int data; Node* next; }; // Function that checks for loop in linked list, // returns address of node inside loop if // present otherwise returns null Node* detectLoop(Node* head) { Node *slow = head, *fast = head; while (slow && fast && fast->next) { slow = slow->next; fast = fast->next->next; // if loop detected then // returning the node address if (slow == fast) { return slow; } } // if no loop found then return NULL return NULL; } // Function for pushing node in linked list void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // Function for calculating minimum cost which // takes integer vector int findMinCost(vector< int > arr) { int avg = arr[0]; // Calculating average for ( int i = 1; i < arr.size(); i++) { avg = (avg + arr[i]) / 2; } int ans = 0; // For calculating sum of absolute // difference for ( int i = 0; i < arr.size(); i++) { ans += abs (avg - arr[i]); } return ans; } // Main function which takes head node address // and returns minimum cost int minimumCost(Node* head) { // For detecting loop Node* temp = detectLoop(head); if (!temp) // Return 0 if no loop found return 0; Node* temp2 = temp->next; vector< int > arr; if (temp->data % 2 == 0) arr.push_back(temp->data); while (temp2 != temp) { // if current data is even // then push it into the vector if (temp2->data % 2 == 0) arr.push_back(temp2->data); temp2 = temp2->next; } // when even numbers are more than 1 if (arr.size() > 1) { return findMinCost(arr); } else { return 0; } } // Driver code int main() { // Start with the empty list Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 10); // Create a loop for testing head->next->next->next->next = head; cout << minimumCost(head); return 0; } |
Java
import java.util.*; // Link list node class Node { int data; Node next; // Constructor Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function that checks for a loop in the linked list, // returns the address of the node inside the loop if // present; otherwise, returns null static Node detectLoop(Node head) { Node slow = head, fast = head; while (slow != null && fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; // if loop detected then // return the node address if (slow == fast) { return slow; } } // if no loop found then return null return null ; } // Function for pushing node in linked list static Node push(Node head, int new_data) { /* allocate node */ Node new_node = new Node(new_data); /* link the old list to the new node */ new_node.next = head; /* return the new head */ return new_node; } // Function for calculating minimum cost which // takes integer list static int findMinCost(List<Integer> arr) { int avg = arr.get( 0 ); // Calculating average for ( int i = 1 ; i < arr.size(); i++) { avg = (avg + arr.get(i)) / 2 ; } int ans = 0 ; // For calculating the sum of absolute difference for ( int i = 0 ; i < arr.size(); i++) { ans += Math.abs(avg - arr.get(i)); } return ans; } // Main function which takes head node address // and returns minimum cost static int minimumCost(Node head) { // For detecting loop Node temp = detectLoop(head); if (temp == null ) // Return 0 if no loop found return 0 ; Node temp2 = temp.next; List<Integer> arr = new ArrayList<>(); if (temp.data % 2 == 0 ) arr.add(temp.data); while (temp2 != temp) { // if the current data is even // then push it into the list if (temp2.data % 2 == 0 ) arr.add(temp2.data); temp2 = temp2.next; } // when even numbers are more than 1 if (arr.size() > 1 ) { return findMinCost(arr); } else { return 0 ; } } // Driver code public static void main(String[] args) { // Start with the empty list Node head = null ; head = push(head, 20 ); head = push(head, 4 ); head = push(head, 15 ); head = push(head, 10 ); // Create a loop for testing head.next.next.next.next = head; System.out.println(minimumCost(head)); } } |
Python3
# Node class for a linked list class Node: def __init__( self , data): self .data = data self . next = None # Function that checks for a loop in a linked list, # returns the address of the node inside the loop if # present, otherwise returns None def detectLoop(head): slow = head fast = head while slow and fast and fast. next : slow = slow. next fast = fast. next . next # If a loop is detected, return the node address if slow = = fast: return slow # If no loop is found, return None return None # Function for pushing a node into a linked list def push(head_ref, new_data): # Allocate a new node new_node = Node(new_data) # Link the old list to the new node new_node. next = head_ref # Move the head to point to the new node head_ref = new_node return head_ref # Function for calculating the minimum cost which # takes an integer list def findMinCost(arr): avg = arr[ 0 ] # Calculating the average for i in range ( 1 , len (arr)): avg = (avg + arr[i]) / / 2 ans = 0 # For calculating the sum of absolute differences for i in range ( len (arr)): ans + = abs (avg - arr[i]) return ans # Main function which takes the head node address # and returns the minimum cost def minimumCost(head): # For detecting a loop temp = detectLoop(head) if not temp: # Return 0 if no loop found return 0 temp2 = temp. next arr = [] if temp.data % 2 = = 0 : arr.append(temp.data) while temp2 ! = temp: # If the current data is even, push it into the list if temp2.data % 2 = = 0 : arr.append(temp2.data) temp2 = temp2. next # When even numbers are more than 1 if len (arr) > 1 : return findMinCost(arr) else : return 0 # Driver code if __name__ = = "__main__" : # Start with an empty list head = None head = push(head, 20 ) head = push(head, 4 ) head = push(head, 15 ) head = push(head, 10 ) # Create a loop for testing head. next . next . next . next = head print (minimumCost(head)) |
C#
using System; using System.Collections.Generic; // Linked list node class Node { public int data; public Node next; } class GFG { // Function that checks for loop in linked list static Node DetectLoop(Node head) { Node slow = head, fast = head; while (slow != null && fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; // if loop detected then returning the node address if (slow == fast) { return slow; } } // if no loop found then return NULL return null ; } // Function for pushing node in the linked list static void Push( ref Node headRef, int newData) { Node newNode = new Node(); newNode.data = newData; newNode.next = headRef; headRef = newNode; } // Function for calculating minimum cost which takes integer list static int FindMinCost(List< int > arr) { int avg = arr[0]; // Calculating average for ( int i = 1; i < arr.Count; i++) { avg = (avg + arr[i]) / 2; } int ans = 0; // For calculating sum of absolute difference for ( int i = 0; i < arr.Count; i++) { ans += Math.Abs(avg - arr[i]); } return ans; } // Main function which takes head node address and returns minimum cost static int MinimumCost(Node head) { // For detecting loop Node temp = DetectLoop(head); if (temp == null ) // Return 0 if no loop found return 0; Node temp2 = temp.next; List< int > arr = new List< int >(); if (temp.data % 2 == 0) arr.Add(temp.data); while (temp2 != temp) { if (temp2.data % 2 == 0) arr.Add(temp2.data); temp2 = temp2.next; } // when even numbers are more than 1 if (arr.Count > 1) { return FindMinCost(arr); } else { return 0; } } // Driver code static void Main() { // Start with the empty list Node head = null ; Push( ref head, 20); Push( ref head, 4); Push( ref head, 15); Push( ref head, 10); // Create a loop for testing head.next.next.next.next = head; Console.WriteLine(MinimumCost(head)); } } |
Javascript
// Javascript code for the above approach // Link list node class Node { // Constructor constructor(data) { this .data = data; this .next = null ; } } // Function that checks for a loop in the linked list, // returns the address of the node inside the loop if // present; otherwise, returns null function detectLoop(head) { let slow = head, fast = head; while (slow != null && fast != null && fast.next != null ) { slow = slow.next; fast = fast.next.next; // if loop detected then // return the node address if (slow == fast) { return slow; } } // if no loop found then return null return null ; } // Function for pushing node in linked list function push(head, new_data) { /* allocate node */ const new_node = new Node(new_data); /* link the old list to the new node */ new_node.next = head; /* return the new head */ return new_node; } // Function for calculating minimum cost which // takes integer list function findMinCost(arr) { let avg = arr[0]; // Calculating average for (let i = 1; i < arr.length; i++) { avg = Math.floor((avg + arr[i]) / 2); } let ans = 0; // For calculating the sum of absolute difference for (let i = 0; i < arr.length; i++) { ans += Math.abs(avg - arr[i]); } return ans; } // Main function which takes head node address // and returns minimum cost function minimumCost(head) { // For detecting loop const temp = detectLoop(head); if (temp == null ) // Return 0 if no loop found return 0; let temp2 = temp.next; const arr = []; if (temp.data % 2 == 0) arr.push(temp.data); while (temp2 != temp) { // if the current data is even // then push it into the list if (temp2.data % 2 == 0) arr.push(temp2.data); temp2 = temp2.next; } // when even numbers are more than 1 if (arr.length > 1) { return findMinCost(arr); } else { return 0; } } // Driver code // Start with the empty list head = null ; head = push(head, 20); head = push(head, 4); head = push(head, 15); head = push(head, 10); // Create a loop for testing head.next.next.next.next = head; console.log(minimumCost(head)); // This code is contributed by ragul21 |
Output
19
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us