Determine if possible to get Array by breaking rod segments into two halves
Given a rod of length L and an array arr[] of length N, the task is to find if it is possible to break the rod N-1 times in segments such that length of all the segments is present in the array. Each time a segment of length x can be broken into two parts of length ⌈x/2⌉ and x – ⌈x/2⌉.
Examples:
Input: L = 1000, N = 1, arr[] = {1000}
Output: YES
Explanation: It is possible to get the array a by performing (N – 1 = 0) 0 operations on rod.Input: L = 1104, N = 2, arr[] = {861, 243}
Output NO
Explanation: N – 1 = 1, i.e. perform 1 operation.
After one operation only possible segments will be {552, 552}, which are not present in given array.Input: L = 6, N = 3, arr[] = {1, 2, 3}
Output: YES
Explanation: number of operations = 3 – 1 = 2.
After one operation only possible array will be {3, 3} .
Now choose first segment (that is 3) and divide it into two parts which are 1 and 2.
After second operation array will be = {1, 2, 3}
( All permutations of {1, 2, 3} are acceptable, because order doesn’t matter )
Approach: The problem can be solved using the heap data structure based on the following idea:
Try to break that segment into two pieces which has the maximum length and not yet found in the array.
Follow the illustration given below for a better understanding:
Illustration:
Consider L = 6, arr[] = {1, 2, 3}
1st Operation:
=> Break 6 into two segments. Two segments are {3, 3}.
=> One 3 is present in array.2nd Operation:
=> Break another 3 into two segments. Two segments are {1, 2}.
=> Both 1 and 2 are present in array.Two operations are finished and all the segment lengths are also present in the array.
Follow the steps mentioned below to implement the idea:
- Put all the elements of the array in a max heap (say pqarr).
- Similarly, maintain a priority queue (let’s say pq) to store segments obtain after cutting rod and put L into the heap.
- Start dividing from length L. At any instance, it will be convenient to consider the largest segment.
- While the max heap (pq) is not empty:
- If the maximum element of pq is smaller than the maximum element of pqarr, then the answer is not possible because that value of pqarr can never be obtained.
- if the maximum element of pq is equal to the maximum element of pqarr, remove it from both the max heaps.
- if the maximum element of pq is larger than the maximum element of pqarr, remove it from pq and break it into two parts. Then insert those two parts in pq back again.
- After the iteration is over if the heaps are empty return that it is possible.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is // possible to arrange the array bool solution( int len, int n, vector< int >& arr) { // To store elements of array // in priorityqueue priority_queue< int > pqarr; // To store segments after each // operation in priorityqueue priority_queue< int > pq; for ( auto i : arr) { pqarr.push(i); } pq.push(len); while (pq.size() > 0) { int elem = pqarr.top(); int cur = pq.top(); pq.pop(); if (elem > cur) { return false ; } if (elem == cur) { pqarr.top(); pqarr.pop(); } else { pq.push(cur / 2); pq.push((cur + 1) / 2); } } return true ; } // Driver code int main() { int L = 6; int N = 3; vector< int > arr = { 2, 1, 3 }; // Function call bool flag = solution(L, N, arr); if (flag) cout << ( "YES" ); else cout << ( "NO" ); return 0; } // This code is contributed by rakeshsahni |
Java
// Java implementation of above approach import java.io.*; import java.util.*; class GFG { // Function to check if it is // possible to arrange the array public static boolean solution( int len, int n, int [] arr) { // To store elements of array // in priorityqueue PriorityQueue<Integer> pqarr = new PriorityQueue<>(Collections.reverseOrder()); // To store segments after each // operation in priorityqueue PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); for ( int i : arr) { pqarr.add(i); } pq.add(len); while (pq.size() > 0 ) { int elem = pqarr.peek(); int cur = pq.poll(); if (elem > cur) { return false ; } if (elem == cur) { pqarr.poll(); } else { pq.add(cur / 2 ); pq.add((cur + 1 ) / 2 ); } } return true ; } // Driver code public static void main(String[] args) { int L = 6 ; int N = 3 ; int [] arr = { 2 , 1 , 3 }; // Function call boolean flag = solution(L, N, arr); if (flag) System.out.println( "YES" ); else System.out.println( "NO" ); } } |
Python3
# Python3 implementation of above approach import bisect # Function to check if it is # possible to arrange the array def solution(length, n, arr): # To store elements of array # in priorityqueue # to implement priority queue, we will use # bisect insort to insert #in the correct position # and pop(-1) to get the top element pqarr = [] # To store segments after each #operation in priorityqueue pq = [] for i in arr: bisect.insort(pqarr, i) bisect.insort(pq, length) while ( len (pq) > 0 ): elem = pqarr[ - 1 ] cur = pq[ - 1 ] pq.pop( - 1 ) if elem > cur: return False if elem = = cur: pqarr.pop( - 1 ) else : bisect.insort(pq, cur / / 2 ) bisect.insort(pq, (cur + 1 ) / / 2 ) return True # Driver Code L = 6 N = 3 arr = [ 2 , 1 , 3 ] # function call flag = solution(L, N, arr) if flag: print ( "YES" ) else : print ( "NO" ) # This code is contributed by phasing17 |
C#
// C# implementation of above approach using System; using System.Collections.Generic; public class GFG { // Function to check if it is // possible to arrange the array public static bool solution( int len, int n, int [] arr) { // To store elements of array // in priorityqueue List< int > pqarr = new List< int >(); // To store segments after each // operation in priorityqueue List< int > pq = new List< int >(); foreach ( int i in arr) { pqarr.Add(i); } pq.Add(len); pqarr.Sort((a, b) => b.CompareTo(a)); pq.Sort((a, b) => b.CompareTo(a)); while (pq.Count > 0) { int elem = pqarr[0]; int cur = pq[0]; pq.RemoveAt(0); if (elem > cur) { return false ; } if (elem == cur) { pqarr.RemoveAt(0); } else { pq.Add(cur / 2); pq.Add((cur + 1) / 2); } pq.Sort((a, b) => b.CompareTo(a)); } return true ; } // Driver code public static void Main(String[] args) { int L = 6; int N = 3; int [] arr = { 2, 1, 3 }; // Function call bool flag = solution(L, N, arr); if (flag) Console.WriteLine( "YES" ); else Console.WriteLine( "NO" ); } } // This code contributed by shikhasingrajput |
Javascript
// JavaScript implementation of above approach // Function to check if it is // possible to arrange the array function solution(len, n, arr) { // To store elements of array // in priorityqueue let pqarr = []; // To store segments after each // operation in priorityqueue let pq = []; for (let i of arr) pqarr.push(i); pq.push(len); pq.sort(); pq.reverse(); pqarr.sort(); pqarr.reverse(); while (pq.length > 0) { let elem = pqarr[0]; let cur = pq[0]; pq.splice(0, 1); if (elem > cur) { return false ; } if (elem == cur) { pqarr.splice(0, 1); } else { pq.push(Math.floor(cur / 2)); pq.push(Math.floor((cur + 1) / 2)); } pq.sort(); pq.reverse(); } return true ; } // Driver code let L = 6; let N = 3; let arr = [ 2, 1, 3 ]; // Function call let flag = solution(L, N, arr); if (flag) console.log( "YES" ); else console.log( "NO" ); // This code is contributed by phasing17 |
YES
Time Complexity: O(N * logN)
Auxiliary Space: O(N)