TCS Codevita | Holes And Balls

Given two arrays of H[] and B[] consisting of N and M integers respectively, denoting the diameter of holes and balls respectively. M number of balls are made to roll from...

Given two arrays of H[] and B[] consisting of N and M integers respectively, denoting the diameter of holes and balls respectively. M number of balls are made to roll from A to B on a sloping surface with N holes, each having different depth as shown in the figure below: The task is to find the eventual position of each ball in the order of the ball released considering the following: A ball will fall into a hole if its diameter is less than or equal to the diameter of the hole. A hole H i will become full if i numbers of balls fall into it. If a hole is full, then no more balls fall into it. A ball will reach B from A , if and only if it is not falling into any one of the holes. If a ball is in hole P i , then its position is i . If a ball reached the bottom point B, then take its position as 0 . Examples:

Input: H[] = {21, 3, 6}, B[] = {20, 15, 5, 7, 10, 4, 2, 1, 3, 6, 8}

Output: 1 0 3 0 0 3 3 2 2 0 0 Explanation: Ball of diameter 20 will fall into the hole H 1 and the hole H 1 will become full. Balls with diameter 15, 7 and 10 will reach bottom, since the hole H 1 is full and diameters of holes H 2 and H 3 are less than the diameters of the balls. Balls with diameters 5, 4 and 2 will fall into the hole H 3 . Ball with diameter 1 will fall into the hole H 2 since the hole H 3 is already full. Ball with diameter 3 will fall into hole H 2 . Balls with diameters 6, and 8 will reach the bottom point B. The position of ball 20 is 1 because it is in hole H 1 . Positions of ball 15, 7, 10, 3, 6, and 8 are 0 because they reached the bottom point B. Therefore, the balls with diameter 5, 4 and 2 are in the 3rd hole H 3 , the ball with diameter 1 and 3 are in the 2nd hole H 2 .

Input: H[] = {20, 15, 10, 5, 25}, B[] = {5, 10, 15, 20, 25, 30, 4, 9, 14, 19}

Output: 5 5 5 5 5 0 4 3 2 1 Approach: Follow the steps below to solve the problem: Initialize an array position[] of size N to store the final position of each ball and an array depth[] of size N to store the capacity of each hole. Iterate over the range [1, N] using the variable i and set the initial depth[i] of the hole[i] to i+1 . Traverse the array ball[] using the variable i and do the following: Initialize flag to False. Iterate over the array hole[] using variable j in reverse order. Check if the diameter of the hole is greater than or equal to that of the ball, i.e., hole[j] ? ball[i] , and if that hole is not full, i.e., depth [j] ? j then, place the ball in that hole by appending j + 1 in the position[] array and incrementing the depth of the hole by 1 and flag equal to True break out of the loop . If the ball doesn't fit in any hole (has reached at end of the slope) the flag will be False, then append 0 in the position[] array. After the above steps, print the value stored in the array position[] as the result. Below is the implementation of the above approach: C++ // C++ program for the above approach #include using namespace std ; // Function to find and print the final // position of balls vector < int > ballPositionFinder ( vector < int > holes , vector < int > balls ){ // Array of zero equal to length of holes array // to store the no. of balls in the hole vector < int > depth ( holes . size (), 0 ); // Stores the positions of balls vector < int > positions ; // Iterate through balls array // and holes array in reverse order. for ( int i : balls ){ // Initialize flag equal to false bool flag = false ; vector < int > array ; for ( int i = 0 ; i < holes . size (); i ++ ){ array . push_back ( i ); } reverse ( array . begin (), array . end ()); for ( auto j : array ) { // Check if the diameter of ball is less than the // diameter of hole and depth is less than the index. if ( i <= holes [ j ] && depth [ j ] <= j ) { // If the condition is true push the position // for ball in position array and increment depth of hole by 1. positions . push_back ( j + 1 ); depth [ j ] += 1 ; // Here the ball will fall into the hole // so make the flag True and break the loop. flag = true ; break ; } } // Check if the ball has reached the bottom // if the ball reaches bottom flag will remain false // so then push 0 to the position array. if ( flag == false ) positions . push_back ( 0 ); }

return positions ; } // Driver Code int main () { vector < int > holes = { 21 , 3 , 6 }; vector < int > balls = { 20 , 15 , 5 , 7 , 10 , 4 , 2 , 1 , 3 , 6 , 8 }; // Function Call vector < int >

output = ballPositionFinder ( holes , balls ); for ( auto i :

output ) cout << i << " " ; } // This code is contributed by shinjanpatra Python3 # Python program for the above approach # Function to find and print the final # position of balls def ballPositionFinder ( holes , balls ): # Array of zero equal to length of holes array # to store the no. of balls in the hole depth = [ 0 for i in range ( len ( holes ))] # Stores the positions of balls positions = [] # Iterate through balls array # and holes array in reverse order. for i in balls : # Initialize flag equal to false flag = False for j in reversed ( range ( len ( holes ))): # Check if the diameter of ball is less than the # diameter of hole and depth is less than the index. if i <= holes [ j ] and depth [ j ] <= j : # If the condition is true append the position # for ball in position array and increment depth of hole by 1. positions . append ( j + 1 ) depth [ j ] += 1 # Here the ball will fall into the hole # so make the flag True and break the loop. flag = True break # Check if the ball has reached the bottom # if the ball reaches bottom flag will remain false # so then append 0 to the position array. if flag == False : positions . append ( 0 )

return positions # Driver Code if name == "main" : holes = [ 21 , 3 , 6 ] balls = [ 20 , 15 , 5 , 7 , 10 , 4 , 2 , 1 , 3 , 6 , 8 ] # Function Call output = ballPositionFinder ( holes , balls ) for i in output : print ( i , end = " " ) Java /package whatever //do not write package name here / import java.io. ; import java.util. ; class GFG { // Java program for the above approach // Function to find and print the final // position of balls static ArrayList < Integer > ballPositionFinder ( int [] holes , int [] balls ){ // Array of zero equal to length of holes array // to store the no. of balls in the hole int [] depth = new int [ holes . length ] ; Arrays . fill ( depth , 0 ); // Stores the positions of balls ArrayList < Integer > positions = new ArrayList <> (); // Iterate through balls array // and holes array in reverse order. for ( int i : balls ){ // Initialize flag equal to false boolean flag = false ; ArrayList < Integer > array = new ArrayList <> (); for ( int j = 0 ; j < holes . length ; j ++ ){ array . add ( j ); } Collections . reverse ( array ); for ( int j : array ) { // Check if the diameter of ball is less than the // diameter of hole and depth is less than the index. if ( i <= holes [ j ] && depth [ j ] <= j ) { // If the condition is true push the position // for ball in position array and increment depth of hole by 1. positions . add ( j + 1 ); depth [ j ] += 1 ; // Here the ball will fall into the hole // so make the flag True and break the loop. flag = true ; break ; } } // Check if the ball has reached the bottom // if the ball reaches bottom flag will remain false // so then push 0 to the position array. if ( flag == false ) positions . add ( 0 ); }

return positions ; } // Driver Code public static void main ( String args [] ) { int [] holes = { 21 , 3 , 6 }; int [] balls = { 20 , 15 , 5 , 7 , 10 , 4 , 2 , 1 , 3 , 6 , 8 }; // Function Call ArrayList < Integer >

output = ballPositionFinder ( holes , balls ); for ( int i :

output ) System . out . print ( i + " " ); } } // code is contributed by shinjanpatra C# using System ; using System.Collections.Generic ; class GFG { // Function to find and print the final // position of balls static List < int > BallPositionFinder ( int [] holes , int [] balls ) { // Array of zero equal to length of holes array // to store the no. of balls in the hole int [] depth = new int [ holes . Length ]; Array . Fill ( depth , 0 ); // Stores the positions of balls List < int > positions = new List < int > (); // Iterate through balls array // and holes array in reverse order. foreach ( int i in balls ) { // Initialize flag equal to false bool flag = false ; List < int > array = new List < int > (); for ( int j = 0 ; j < holes . Length ; j ++ ) { array . Add ( j ); } array . Reverse (); foreach ( int j in array ) { // Check if the diameter of ball is less than the // diameter of hole and depth is less than the index. if ( i <= holes [ j ] && depth [ j ] <= j ) { // If the condition is true push the position // for ball in position array and increment depth of hole by 1. positions . Add ( j + 1 ); depth [ j ] += 1 ; // Here the ball will fall into the hole // so make the flag True and break the loop. flag = true ; break ; } } // Check if the ball has reached the bottom // if the ball reaches bottom flag will remain false // so then push 0 to the position array. if ( flag == false ) positions . Add ( 0 ); }

return positions ; } // Driver Code static void Main () { int [] holes = { 21 , 3 , 6 }; int [] balls = { 20 , 15 , 5 , 7 , 10 , 4 , 2 , 1 , 3 , 6 , 8 }; // Function Call List < int >

output = BallPositionFinder ( holes , balls ); foreach ( int i in output ) Console . Write ( i + " " ); } } JavaScript < script > // JavaScript program for the above approach // Function to find and print the final // position of balls function ballPositionFinder ( holes , balls ){ // Array of zero equal to length of holes array // to store the no. of balls in the hole let depth = new Array ( holes . length ). fill ( 0 ) // Stores the positions of balls let positions = [] // Iterate through balls array // and holes array in reverse order. for ( let i of balls ){ // Initialize flag equal to false let flag = false let array = [] for ( let i = 0 ; i < holes . length ; i ++ ){ array . push ( i ) } array . reverse () for ( let j of array ) { // Check if the diameter of ball is less than the // diameter of hole and depth is less than the index. if ( i <= holes [ j ] && depth [ j ] <= j ) { // If the condition is true push the position // for ball in position array and increment depth of hole by 1. positions . push ( j + 1 ) depth [ j ] += 1 // Here the ball will fall into the hole // so make the flag True and break the loop. flag = true break } } // Check if the ball has reached the bottom // if the ball reaches bottom flag will remain false // so then push 0 to the position array. if ( flag == false ) positions . push ( 0 ) }

return positions } // Driver Code let holes = [ 21 , 3 , 6 ] let balls = [ 20 , 15 , 5 , 7 , 10 , 4 , 2 , 1 , 3 , 6 , 8 ] // Function Call let output = ballPositionFinder ( holes , balls ) for ( let i of output ) document . write ( i , " " ) // This code is contributed by shinjanpatra < /script>

Output 1 0 3 0 0 3 3 2 2 0 0 Time Complexity: O(N*M) Auxiliary Space: O(N)