Placement of magical box on road to collect the maximum number of magical balls
There is a road which denotes the x-axis. Geek is at the start of the road (at origin). He has N magical balls. The balls are magical because they have a number written on them and they go that number of positions on every bounce. if the ball has 4 written on it, it goes to the positions like 4, 8, 12, 16, . . . . As Geek has N number of magical balls he throws them one by one starting at 0 position. You have a magical box that can hold an infinite number of balls, the task is to place that magical box on the road such that you collect the maximum number of magical balls. But you have only one chance of placing the box. Also, you can only place the box at the Kth position on the road. You know the values of every magical ball. You are given an integer N number of magical balls, an array containing the values of every ball, K(N, K values lie between 1 to 2*10^5) denoting the last position where you can place the box.
Note: The value of the number written on every ball is between 1 to 10^5.
Examples:
Input: arr[] = {2, 2, 4, 9, 10, 4, 6, 5, 3, 8}, N = 10, K = 8
Output: 5
Explanation: We can place the box at position 8 where balls 2, 2, 4, 4, and 8 come and fall.Input: arr[] = {1, 3, 2, 1, 5, 5}, N = 6, K = 10
Output: 5
Explanation: We can place the box at position 10 where balls 1, 1, 5, 5, and 2 come and fall.
Approach: To solve the problem follow the below observations:
Observations:
- Our answer depends on the balls that are less than or equal to K as we can collect balls till K position only.
- So, we can remove balls greater than K from our consideration.
Steps to solve the problem:
- To solve this problem, we can take two arrays of size k+1 as we need to consider position k also.
- We put the frequencies of every ball into those two arrays. Because there can be multiple balls of same number written on them.
- Then we iterate over the positions from 1 to k. At every position we check for the balls which have current position number on them.
- If the balls count is zero in the array, we continue for next position.
- Else, we take the number of that ball and iterate over it’s multiples and add the balls frequency to it’s multiple’s positions. Like if we have ball number 2 and it’s frequency is 3, we add 3 to it’s all multiples which lie under k.
- To know the initial frequency of given balls, we maintain two arrays. Array 1 has the frequencies of the balls and we don’t modify it further.
- In array-2, we modify it as per we do adding operations of multiples.
- In Summary, in this approach we take a ball’s count frequency from array1 and we go on adding it’s frequency to it’s multiples less then or equal to k position. Then the maximum value of array2 is our answer.
Below is the code of above approach which describes the approach clearly.
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to calculate answer int countBalls( int balls[], int N, int K) { // Arrays of size K+1 // Array1 to keep initial freqencies vector< int > arr1(K + 1); // Array2 to modify during operations vector< int > arr2(K + 1); // answer to return int ans = 0; // segregate the balls // count the freq of every ball for ( int i = 0; i < N; i++) { // not consider balls >K if (balls[i] > K) continue ; arr1[balls[i]]++; arr2[balls[i]]++; } // Go over every position for ( int i = 1; i <= K; i++) { // We want max balls ans = max(ans, arr2[i]); // If we don't have i position // ball ignore. if (arr1[i] == 0) continue ; // loop over i multiples for ( int j = 2 * i; j <= K; j += i) { // drop all the aee1[i] balls // into it's multiple position balls. arr2[j] += arr1[i]; } } return ans; } // Drivers code int main() { int N = 10, K = 8; int balls[] = { 2, 2, 4, 9, 10, 4, 6, 5, 3, 8 }; // Function Call cout << countBalls(balls, N, K) << '\n' ; return 0; } |
Java
import java.util.*; public class GFG { // Function to calculate answer static int countBalls( int [] balls, int N, int K) { // Arrays of size K+1 // Array1 to keep initial frequencies int [] arr1 = new int [K + 1 ]; // Array2 to modify during operations int [] arr2 = new int [K + 1 ]; // answer to return int ans = 0 ; // segregate the balls // count the frequency of every ball for ( int i = 0 ; i < N; i++) { // not consider balls > K if (balls[i] > K) continue ; arr1[balls[i]]++; arr2[balls[i]]++; } // Go over every position for ( int i = 1 ; i <= K; i++) { // we want max balls ans = Math.max(ans, arr2[i]); // If we don't have i position ball ignore. if (arr1[i] == 0 ) continue ; // loop over i multiples for ( int j = 2 * i; j <= K; j += i) { // drop all the arr1[i] balls // into its multiple position balls. arr2[j] += arr1[i]; } } return ans; } public static void main(String[] args) { int N = 10 , K = 8 ; int [] balls = { 2 , 2 , 4 , 9 , 10 , 4 , 6 , 5 , 3 , 8 }; // Function Call System.out.println(countBalls(balls, N, K)); N = 6 ; K = 10 ; int [] balls1 = { 1 , 3 , 2 , 1 , 5 , 5 }; System.out.println(countBalls(balls1, N, K)); } } |
Python3
def count_balls(balls, N, K): # Arrays of size K+1 # Array1 to keep initial frequencies arr1 = [ 0 for _ in range (K + 1 )] # Array2 to modify during operations arr2 = [ 0 for _ in range (K + 1 )] # answer to return ans = 0 # segregate the balls # count the frequency of every ball for i in range (N): # not consider balls > K if balls[i] > K: continue arr1[balls[i]] + = 1 arr2[balls[i]] + = 1 # Go over every position for i in range ( 1 , K + 1 ): # we want max balls ans = max (ans, arr2[i]) # If we don't have i position ball, ignore. if arr1[i] = = 0 : continue # loop over i multiples for j in range ( 2 * i, K + 1 , i): # drop all the arr1[i] balls # into its multiple position balls. arr2[j] + = arr1[i] return ans if __name__ = = "__main__": N = 10 K = 8 balls = [ 2 , 2 , 4 , 9 , 10 , 4 , 6 , 5 , 3 , 8 ] # Function Call print (count_balls(balls, N, K)) N = 6 K = 10 balls1 = [ 1 , 3 , 2 , 1 , 5 , 5 ] print (count_balls(balls1, N, K)) |
C#
using System; using System.Collections.Generic; class Program { // Function to calculate answer static int CountBalls( int [] balls, int N, int K) { // List of size K+1 // List to keep initial frequencies List< int > arr1 = new List< int >( new int [K + 1]); // List to modify during operations List< int > arr2 = new List< int >( new int [K + 1]); // answer to return int ans = 0; // segregate the balls // count the frequency of every ball for ( int i = 0; i < N; i++) { if (balls[i] > K) continue ; arr1[balls[i]]++; arr2[balls[i]]++; } // Go over every position for ( int i = 1; i <= K; i++) { // we want max balls ans = Math.Max(ans, arr2[i]); // If we don't have i position ball ignore. if (arr1[i] == 0) continue ; for ( int j = 2 * i; j <= K; j += i) { // drop all the arr1[i] balls // into its multiple position balls. arr2[j] += arr1[i]; } } return ans; } static void Main() { int N = 10, K = 8; int [] balls = { 2, 2, 4, 9, 10, 4, 6, 5, 3, 8 }; // Function Call Console.WriteLine(CountBalls(balls, N, K)); } } |
Javascript
// JavaScript code for the above approach: // Function to calculate answer function countBalls(balls, N, K) { // Arrays of size K+1 // Array1 to keep initial frequencies let arr1 = new Array(K + 1).fill(0); // Array2 to modify during operations let arr2 = new Array(K + 1).fill(0); // answer to return let ans = 0; // Segregate the balls //count the freq of every ball for (let i = 0; i < N; i++) { // not consider balls > K if (balls[i] > K) continue ; arr1[balls[i]]++; arr2[balls[i]]++; } // Go over every position for (let i = 1; i <= K; i++) { // We want max balls ans = Math.max(ans, arr2[i]); // If we don't have the i position //ball ignore. if (arr1[i] === 0) continue ; // loop over i multiples for (let j = 2 * i; j <= K; j += i) { // drop all the arr1[i] balls //into it's multiple position balls arr2[j] += arr1[i]; } } return ans; } // Driver code const N = 10; const K = 8; const balls = [2, 2, 4, 9, 10, 4, 6, 5, 3, 8]; // Function Call console.log(countBalls(balls, N, K)); |
5
Time Complexity: O(N + Klog(K)), where N is for frequency counting of balls and KlogK for the second loop.
Auxiliary Space: O(2k), for two extra arrays.
Contact Us