Understand Put Marbles in Bags Problem

Problem Name: Put Marbles in Bags
Problem Description:

Problem: Put Marbles in Bags

Difficulty: Hard

Problem Statement :

You have k bags and are given a 0-indexed integer array weights where weights[i] represents the weight of the iᵗʰ marble. Your task is to divide the marbles into the k bags following these rules:

  1. No bag is empty.
  2. Contiguous Assignment: If the iᵗʰ and jᵗʰ marbles are in a bag, then all marbles with indices between i and j must also be in that bag.
  3. Bag Cost: If a bag contains marbles from index i to j inclusively, its cost is calculated as weights[i] + weights[j].

The score after distributing the marbles is the sum of the costs of all k bags.

Objective: Return the difference between the maximum and minimum scores achievable through different valid distributions of the marbles.

Examples

Example 1:

Input:

weights = [1,3,5,1], k = 2

Output:

4

Explanation:

  • Minimal score distribution: [1], [3,5,1] → (1+1) + (3+1) = 6
  • Maximal score distribution: [1,3], [5,1] → (1+3) + (5+1) = 10 Difference: 10 - 6 = 4

Input:

weights = [1, 3], k = 2

Output:

0

Explanation:

  • The only possible distribution is [1], [3], resulting in the same score for both maximum and minimum.
Category:
  • Sorting
  • Arrays
Programming Language:
  • Java
Reference Link:

https://leetcode.com/problems/put-marbles-in-bags/description/

Online IDE

Scroll down for output
Java
Output:
Loading component...
Loading component...
Tracking code (View only. In case you want to track the code, click this button):
Main Function:
INPUT :  weights = [1,3,5,1], k = 2
OUTPUT :  4
public static void main(String[] args) {
int[] weights1 = {1, 3, 5, 1};
int k1 = 2;
System.out.println(putMarbles(weights1, k1));
int[] weights2 = {1, 3};
int k2 = 2;
System.out.println(putMarbles(weights2, k2));
} //Function End
Helper Function:
public static long putMarbles(int[] weights, int k) {
 int n = weights.length;
 if (k == 1){
return 0;
}//If End
long[] pairSums = new long[n - 1];
 for (int i = 0; i < n - 1; i++) {
 pairSums[i] = weights[i] + weights[i + 1];
}//Loop End
Arrays.sort(pairSums);
long minScore = 0, maxScore = 0;
for (int i = 0; i < k - 1; i++) {
 minScore += pairSums[i];    
maxScore += pairSums[n - 2 - i]; 
}//Loop End
 return maxScore - minScore;
} // Function End
Utility Functions and Global variables:
Utility Function is not required.
Privacy Policy | About