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 ith 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 placedvoid 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 codeint 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 approachclass 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 approachimport bisect# Function to print the position of each boxes# where a ball has to be placeddef 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 codeA = [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 approachusing 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 boundfunction 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
