Find the position of box which occupies the given ball

0 0 6 minutes read

Given two array A[] and B[]. Where size of A[] represent the number of rows and A[i] represent the number of boxes in the i^th row. Array B[] represents an array of balls where B[i] represents a number on the ball. Given that ball i (having value B[i]) will be placed in a box whose position from beginning is B[i] (row-major). The task is to find the row and column of the boxes corresponding to each B[i].
Examples:

Input: A[] = {2, 3, 4, 5}, B[] = {1, 4, 6, 3}
Output:
1, 1
2, 2
3, 1
2, 1
B[0] = 1, hence Box position will be 1st row, 1st column
B[1] = 4, hence Box position will be 2nd row, 2nd column
B[2] = 6, hence Box position will be 3rd row, 1st column
B[3] = 3, hence Box position will be 2nd row, 1st column
Input: A[] = {2, 2, 2, 2}, B[] = {1, 2, 3, 4}
Output:
1, 1
1, 2
2, 1
2, 2

Approach: As per problem statement, in 1st row A[0] number of boxes are placed similarly in 2nd row A[1] number of boxes are there. So, in case a ball is to be placed in any box of the second row, its value must be greater than A[0]. So, for finding the actual position of box where a ball B[i] is going to be placed first of all find the cumulative sum of array A[] and then find the position of element in cumulative sum array which is just greater than B[i], that will be the row number and for finding the box number in that particular row find the value of B[i] – value in cumulative array which is just smaller than B[i].
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the position of each boxes
// where a ball has to be placed
void printPosition(int A[], int B[], int sizeOfA, int sizeOfB)
{
 
    // Find the cumulative sum of array A[]
    for (int i = 1; i < sizeOfA; i++)
        A[i] += A[i - 1];
 
    // Find the position of box for each ball
    for (int i = 0; i < sizeOfB; i++) {
 
        // Row number
        int row = lower_bound(A, A + sizeOfA, B[i]) - A;
 
        // Column (position of box in particular row)
        int boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
 
        // Row + 1 denotes row if indexing of array start from 1
        cout << row + 1 << ", " << boxNumber << "\n";
    }
}
 
// Driver code
int main()
{
 
    int A[] = { 2, 2, 2, 2 };
    int B[] = { 1, 2, 3, 4 };
    int sizeOfA = sizeof(A) / sizeof(A[0]);
    int sizeOfB = sizeof(B) / sizeof(B[0]);
    printPosition(A, B, sizeOfA, sizeOfB);
 
    return 0;
}

Java

// Java implementation of the approach
 
class GFG
{
 
    // Function to print the position of each boxes 
    // where a ball has to be placed 
    static void printPosition(int A[], int B[], 
                        int sizeOfA, int sizeOfB) 
    {
 
        // Find the cumulative sum of array A[] 
        for (int i = 1; i < sizeOfA; i++) 
        {
            A[i] += A[i - 1];
        }
 
        // Find the position of box for each ball 
        for (int i = 0; i < sizeOfB; i++)
        {
 
            // Row number 
            int row = lower_bound(A, 0, A.length, B[i]);
 
            // Column (position of box in particular row) 
            int boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
 
            // Row + 1 denotes row if indexing of array start from 1 
            System.out.print(row + 1 + ", " + boxNumber + "\n");
        }
    }
 
    private static int lower_bound(int[] a, int low, int high, int element)
    {
        while (low < high)
        {
            int middle = low + (high - low) / 2;
            if (element > a[middle])
            {
                low = middle + 1;
            }
            else
            {
                high = middle;
            }
        }
        return low;
    }
    // Driver code 
    public static void main(String[] args)
    {
        int A[] = {2, 2, 2, 2};
        int B[] = {1, 2, 3, 4};
        int sizeOfA = A.length;
        int sizeOfB = B.length;
        printPosition(A, B, sizeOfA, sizeOfB);
 
    }
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
import bisect
 
# Function to print the position of each boxes
# where a ball has to be placed
def printPosition(A, B, sizeOfA, sizeOfB):
 
    # Find the cumulative sum of array A[]
    for i in range(1, sizeOfA):
        A[i] += A[i - 1]
 
    # Find the position of box for each ball
    for i in range(sizeOfB):
 
        # Row number
        row = bisect.bisect_left(A, B[i])
 
        # Column (position of box in particular row)
        if row >= 1:
            boxNumber = B[i] - A[row - 1]
        else:
            boxNumber = B[i]
 
        # Row + 1 denotes row 
        # if indexing of array start from 1
        print(row + 1, ",", boxNumber)
 
# Driver code
A = [2, 2, 2, 2]
B = [1, 2, 3, 4]
sizeOfA = len(A)
sizeOfB = len(B)
printPosition(A, B, sizeOfA, sizeOfB)
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to print the position of each boxes 
    // where a ball has to be placed 
    static void printPosition(int []A, int []B, 
                        int sizeOfA, int sizeOfB) 
    {
 
        // Find the cumulative sum of array A[] 
        for (int i = 1; i < sizeOfA; i++) 
        {
            A[i] += A[i - 1];
        }
 
        // Find the position of box for each ball 
        for (int i = 0; i < sizeOfB; i++)
        {
 
            // Row number 
            int row = lower_bound(A, 0, A.Length, B[i]);
 
            // Column (position of box in particular row) 
            int boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
 
            // Row + 1 denotes row if indexing of array start from 1 
            Console.WriteLine(row + 1 + ", " + boxNumber + "\n");
        }
    }
 
    private static int lower_bound(int[] a, int low,
                                    int high, int element)
    {
        while (low < high)
        {
            int middle = low + (high - low) / 2;
            if (element > a[middle])
            {
                low = middle + 1;
            }
            else
            {
                high = middle;
            }
        }
        return low;
    }
     
    // Driver code 
    static public void Main ()
    {
        int []A = {2, 2, 2, 2};
        int []B = {1, 2, 3, 4};
        int sizeOfA = A.Length;
        int sizeOfB = B.Length;
        printPosition(A, B, sizeOfA, sizeOfB);
 
    }
}
 
// This code has been contributed by Tushil.

PHP

<?php
 
// function to find the lower bound
function lower_bound($A, $valueTosearch)
{
    $row = 0;
    foreach ($A as $key=>$value)
    {
        if($valueTosearch <= $value)
            return $row;
        $row++;
    }
    return $row+1;
}
 
// Function to print the position of each boxes 
// where a ball has to be placed 
function printPosition($A, $B, $sizeOfA, $sizeOfB) 
{ 
 
    // Find the cumulative sum of array A[] 
    for ($i = 1; $i <$sizeOfA; $i++) 
        $A[$i] += $A[$i - 1]; 
 
    // Find the position of box for each ball 
    for ($i = 0; $i < $sizeOfB; $i++)
    { 
 
        // Row number 
        $row = lower_bound($A, $B[$i]) ;
 
        // Column (position of box in particular row) 
        $boxNumber = ($row >= 1) ? $B[$i] - $A[$row - 1] : $B[$i]; 
 
        // Row + 1 denotes row if indexing of array start from 1 
        print_r($row+1 .", ".$boxNumber); 
        echo "\n";
    } 
} 
 
    // Driver code
    $A = array(2, 2, 2, 2 ); 
    $B = array( 1, 2, 3, 4 ); 
    $sizeOfA =count($A); 
    $sizeOfB = count($B); 
    printPosition($A, $B, $sizeOfA, $sizeOfB); 
     
    // This code is contributed by Shivam.Pradhan
?>

Javascript

<script>
// javascript implementation of the approach
    // Function to print the position of each boxes
    // where a ball has to be placed
    function printPosition(A , B , sizeOfA , sizeOfB) {
 
        // Find the cumulative sum of array A
        for (i = 1; i < sizeOfA; i++) {
            A[i] += A[i - 1];
        }
 
        // Find the position of box for each ball
        for (i = 0; i < sizeOfB; i++) {
 
            // Row number
            var row = lower_bound(A, 0, A.length, B[i]);
 
            // Column (position of box in particular row)
            var boxNumber = (row >= 1) ? B[i] - A[row - 1] : B[i];
 
            // Row + 1 denotes row if indexing of array start from 1
            document.write(row + 1 + ", " + boxNumber + "<br/>");
        }
    }
 
     function lower_bound(a , low , high , element) {
        while (low < high) {
            var middle = low + (high - low) / 2;
            if (element > a[middle]) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        return low;
    }
 
    // Driver code
     
        var A = [ 2, 2, 2, 2 ];
        var B = [ 1, 2, 3, 4 ];
        var sizeOfA = A.length;
        var sizeOfB = B.length;
        printPosition(A, B, sizeOfA, sizeOfB);
 
 
// This code contributed by gauravrajput1 
</script>

Output:

1, 1
1, 2
2, 1
2, 2

Time Complexity: O(sizeOfA + sizeOfB)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!