Given an array arr[] of length n, where arr[i] is the number of soldiers in the i-th troop, and an integer k. A troop is called lucky if its soldier count is a multiple of k. Find the minimum total number of soldiers to add across all troops so that at least ⌈n / 2⌉ troops become lucky. You may add any number of soldiers to any troop.
Examples:
Input: arr[] = [3, 5, 6, 7, 9, 10], k = 4
Output: 4
Explanation: We need at least 3 lucky troops since ⌈ 6 / 2 ⌉ = 3.
Currently, no troop is divisible by 4.
Add 1 soldier for troop 3 → 4,
Add 2 for troop 6 → 8,
Add 1 for troop 7 → 8.
New array: [4, 5, 8, 8, 9, 10] with 3 lucky troops (4, 8, 8).
Total soldiers added = 4.Input: arr[] = [5, 6, 3, 2, 1], k = 2
Output: 1
Explanation: Add 1 soldier to the troop with 1 soldier → arr = [5, 6, 3, 2, 2].
Now 3 troops (6, 2, and 2) are divisible by 2. Since ⌈ 5/2 ⌉ = 3, the requirement is met.
Try it on GfG Practice
Table of Content
[Naive Approach] Generating All Sub Set - O(n * 2n) Time and O(1) Space
The main idea is to try all possible subset of troops that could be made lucky and calculate the minimum total number of soldiers needed.
For each selected troop, if its current count arr[i] is not divisible by k, we compute the number of soldiers to add as k - (arr[i] % k), this is the smallest amount needed to reach the next multiple of k.
We sum up these additions for each valid combination and pick the one with the least total soldiers added.
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Check if a troop is already lucky
bool isLucky(int num, int k) {
return num % k == 0;
}
int minSoldiers(vector<int>& arr, int k) {
int n = arr.size();
// Number of troops that need to be lucky
int need = (n + 1) / 2;
int minCost = INT_MAX;
// Total combinations to try
// (each troop can be included or excluded)
int totalComb = 1 << n;
// Try all subsets of troops
for (int mask = 0; mask < totalComb; ++mask) {
int count = 0;
int cost = 0;
for (int i = 0; i < n; ++i) {
if (mask & (1 << i)) {
++count;
if (!isLucky(arr[i], k)) {
// Add soldiers to make arr[i] a multiple of k
cost += (k - (arr[i] % k));
}
}
}
if (count >= need) {
minCost = min(minCost, cost);
}
}
return minCost;
}
int main() {
vector<int> arr = {3, 5, 6, 7, 9, 11};
int k = 4;
cout << minSoldiers(arr, k) << endl;
return 0;
}
import java.util.ArrayList;
import java.util.List;
class GfG {
// Check if a troop is already lucky
static boolean isLucky(int num, int k) {
return num % k == 0;
}
static int minSoldiers(int[] arr, int k) {
int n = arr.length;
// Number of troops that need to be lucky
int need = (n + 1) / 2;
int minCost = Integer.MAX_VALUE;
// Total combinations to try
// (each troop can be included or excluded)
int totalComb = 1 << n;
// Try all subsets of troops
for (int mask = 0; mask < totalComb; ++mask) {
int count = 0;
int cost = 0;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
++count;
if (!isLucky(arr[i], k)) {
// Add soldiers to make arr[i] a multiple of k
cost += (k - (arr[i] % k));
}
}
}
if (count >= need) {
minCost = Math.min(minCost, cost);
}
}
return minCost;
}
public static void main(String[] args) {
int[] arr = {3, 5, 6, 7, 9, 11};
int k = 4;
System.out.println(minSoldiers(arr, k));
}
}
from typing import List
# Check if a troop is already lucky
def isLucky(num: int, k: int) -> bool:
return num % k == 0
def minSoldiers(arr: List[int], k: int) -> int:
n = len(arr)
# Number of troops that need to be lucky
need = (n + 1) // 2
minCost = float('inf')
# Total combinations to try
# (each troop can be included or excluded)
totalComb = 1 << n
# Try all subsets of troops
for mask in range(totalComb):
count = 0
cost = 0
for i in range(n):
if mask & (1 << i):
count += 1
if not isLucky(arr[i], k):
# Add soldiers to make arr[i] a multiple of k
cost += (k - (arr[i] % k))
if count >= need:
minCost = min(minCost, cost)
return minCost
if __name__ == '__main__':
arr = [3, 5, 6, 7, 9, 11]
k = 4
print(minSoldiers(arr, k))
using System;
using System.Collections.Generic;
public class GfG {
// Check if a troop is already lucky
static bool isLucky(int num, int k) {
return num % k == 0;
}
static int minSoldiers(int[] arr, int k) {
int n = arr.Length;
// Number of troops that need to be lucky
int need = (n + 1) / 2;
int minCost = int.MaxValue;
// Total combinations to try
// (each troop can be included or excluded)
int totalComb = 1 << n;
// Try all subsets of troops
for (int mask = 0; mask < totalComb; ++mask) {
int count = 0;
int cost = 0;
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
++count;
if (!isLucky(arr[i], k)) {
// Add soldiers to make arr[i] a multiple of k
cost += (k - (arr[i] % k));
}
}
}
if (count >= need) {
minCost = Math.Min(minCost, cost);
}
}
return minCost;
}
public static void Main() {
int[] arr = new int[] { 3, 5, 6, 7, 9, 11 };
int k = 4;
Console.WriteLine(minSoldiers(arr, k));
}
}
function isLucky(num, k) {
return num % k === 0;
}
function minSoldiers(arr, k) {
const n = arr.length;
// Number of troops that need to be lucky
const need = Math.ceil(n / 2);
let minCost = Number.MAX_SAFE_INTEGER;
// Total combinations to try
// (each troop can be included or excluded)
const totalComb = 1 << n;
// Try all subsets of troops
for (let mask = 0; mask < totalComb; ++mask) {
let count = 0;
let cost = 0;
for (let i = 0; i < n; ++i) {
if (mask & (1 << i)) {
++count;
if (!isLucky(arr[i], k)) {
// Add soldiers to make arr[i] a multiple of k
cost += (k - (arr[i] % k));
}
}
}
if (count >= need) {
minCost = Math.min(minCost, cost);
}
}
return minCost;
}
// Driver Code
const arr = [3, 5, 6, 7, 9, 11];
const k = 4;
console.log(minSoldiers(arr, k));
[Expected Approach - 1] Using Sorting - O(n log(n)) Time and O(n) Space
The idea is to calculate how many soldiers need to be added to each troop to make it lucky, means divisible by k. If a troop is already lucky, the cost is zero. Otherwise, the cost to make it lucky is calculated as k - (arr[i] % k). We collect these costs for all troops and sort them in increasing order. Since we need at least half of the troops to be lucky, we select the smallest ceil(n / 2) costs and add them.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int minSoldiers(vector<int>& arr, int k) {
int n = arr.size();
int need = (n + 1) / 2;
vector<int> costs;
for (int num : arr) {
if (num % k == 0) {
costs.push_back(0);
} else {
costs.push_back(k - (num % k));
}
}
// Sort the costs in ascending order
sort(costs.begin(), costs.end());
// Add up the smallest `need` costs
int total = 0;
for (int i = 0; i < need; ++i) {
total += costs[i];
}
return total;
}
int main() {
vector<int> arr = {3, 5, 6, 7, 9, 11};
int k = 4;
cout << minSoldiers(arr, k) << endl;
return 0;
}
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
public class GfG {
public static int minSoldiers(int[] arr, int k) {
int n = arr.length;
int need = (n + 1) / 2;
List<Integer> costs = new ArrayList<>();
for (int num : arr) {
if (num % k == 0) {
costs.add(0);
} else {
costs.add(k - (num % k));
}
}
// Sort the costs in ascending order
costs.sort(null);
// Add up the smallest `need` costs
int total = 0;
for (int i = 0; i < need; ++i) {
total += costs.get(i);
}
return total;
}
public static void main(String[] args) {
int[] arr = {3, 5, 6, 7, 9, 11};
int k = 4;
System.out.println(minSoldiers(arr, k));
}
}
def minSoldiers(arr, k):
n = len(arr)
need = (n + 1) // 2
costs = []
for num in arr:
if num % k == 0:
costs.append(0)
else:
costs.append(k - (num % k))
# Sort the costs in ascending order
costs.sort()
# Add up the smallest `need` costs
total = sum(costs[:need])
return total
if __name__ == '__main__':
arr = [3, 5, 6, 7, 9, 11]
k = 4
print(minSoldiers(arr, k))
using System;
using System.Collections.Generic;
using System.Linq;
public class GfG {
public static int minSoldiers(int[] arr, int k) {
int n = arr.Length;
int need = (n + 1) / 2;
List<int> costs = new List<int>();
foreach (int num in arr) {
if (num % k == 0) {
costs.Add(0);
}
else {
costs.Add(k - (num % k));
}
}
// Sort the costs in ascending order
costs.Sort();
// Add up the smallest `need` costs
int total = 0;
for (int i = 0; i < need; ++i) {
total += costs[i];
}
return total;
}
public static void Main() {
int[] arr = { 3, 5, 6, 7, 9, 11 };
int k = 4;
Console.WriteLine(minSoldiers(arr, k));
}
}
function minSoldiers(arr, k) {
let n = arr.length;
let need = Math.floor((n + 1) / 2);
let costs = [];
for (let num of arr) {
if (num % k === 0) {
costs.push(0);
} else {
costs.push(k - (num % k));
}
}
// Sort the costs in ascending order
costs.sort((a, b) => a - b);
// Add up the smallest `need` costs
let total = 0;
for (let i = 0; i < need; ++i) {
total += costs[i];
}
return total;
}
// Driver Code
let arr = [3, 5, 6, 7, 9, 11];
let k = 4;
console.log(minSoldiers(arr, k));
[Expected Approach 2] Using Min Heap
We can further optimize by first counting how many troops are already lucky. If that’s enough, we return zero. Otherwise, we compute costs only for the unlucky troops and pick the smallest ones needed to reach the target, avoiding full sorting.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int minSoldiers(vector<int>& arr, int k) {
int n = arr.size();
int need = (n + 1) / 2;
int lucky = 0;
// Min-heap for storing costs to make a troop lucky
priority_queue<int, vector<int>, greater<int>> pq;
for (int num : arr) {
if (num % k == 0) {
++lucky;
} else {
pq.push(k - (num % k));
}
}
// If already enough lucky troops, cost is 0
if (lucky >= need) return 0;
int total = 0;
int req = need - lucky;
// Take smallest required costs from heap
for (int i = 0; i < req && !pq.empty(); ++i) {
total += pq.top();
pq.pop();
}
return total;
}
int main() {
vector<int> arr = {3, 5, 6, 7, 9, 11};
int k = 4;
cout << minSoldiers(arr, k) << endl;
return 0;
}
import java.util.PriorityQueue;
public class GfG {
public static int minSoldiers(int[] arr, int k) {
int n = arr.length;
int need = (n + 1) / 2;
int lucky = 0;
// Min-heap for storing costs to make a troop lucky
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int num : arr) {
if (num % k == 0) {
++lucky;
} else {
pq.add(k - (num % k));
}
}
// If already enough lucky troops, cost is 0
if (lucky >= need) return 0;
int total = 0;
int req = need - lucky;
// Take smallest `required` costs from heap
for (int i = 0; i < req && !pq.isEmpty(); ++i) {
total += pq.poll();
}
return total;
}
public static void main(String[] args) {
int[] arr = {3, 5, 6, 7, 9, 11};
int k = 4;
System.out.println(minSoldiers(arr, k));
}
}
import heapq
def minSoldiers(arr, k):
n = len(arr)
need = (n + 1) // 2
lucky = 0
# Min-heap for storing costs to make a troop lucky
pq = []
for num in arr:
if num % k == 0:
lucky += 1
else:
heapq.heappush(pq, k - (num % k))
# If already enough lucky troops, cost is 0
if lucky >= need:
return 0
total = 0
required = need - lucky
# Take smallest `required` costs from heap
for _ in range(required):
if pq:
total += heapq.heappop(pq)
return total
if __name__ == "__main__":
arr = [3, 5, 6, 7, 9, 11]
k = 4
print(minSoldiers(arr, k))
using System;
using System.Collections.Generic;
public class GfG {
public static int minSoldiers(int[] arr, int k) {
int n = arr.Length;
int need = (n + 1) / 2;
int lucky = 0;
// Min-heap for storing costs to make a troop lucky
SortedSet<int> pq = new SortedSet<int>();
foreach (int num in arr) {
if (num % k == 0) {
lucky++;
} else {
pq.Add(k - (num % k));
}
}
// If already enough lucky troops, cost is 0
if (lucky >= need) return 0;
int total = 0;
int required = need - lucky;
// Take smallest `required` costs from heap
for (int i = 0; i < required && pq.Count > 0; i++) {
total += pq.Min;
pq.Remove(pq.Min);
}
return total;
}
public static void Main() {
int[] arr = {3, 5, 6, 7, 9, 11};
int k = 4;
Console.WriteLine(minSoldiers(arr, k));
}
}
function minSoldiers(arr, k) {
let n = arr.length;
let need = Math.floor((n + 1) / 2);
let lucky = 0;
// Min-heap for storing costs to make a troop lucky
let pq = [];
for (let num of arr) {
if (num % k === 0) {
lucky++;
} else {
pq.push(k - (num % k));
pq.sort((a, b) => a - b);
}
}
// If already enough lucky troops, cost is 0
if (lucky >= need) return 0;
let total = 0;
let required = need - lucky;
// Take smallest `required` costs from heap
for (let i = 0; i < required && pq.length > 0; i++) {
total += pq.shift();
}
return total;
}
// Driver Code
let arr = [3, 5, 6, 7, 9, 11];
let k = 4;
console.log(minSoldiers(arr, k));
Time Complexity: O(n + m * log(m)), where m is the number of unlucky troops (at most n).
Auxiliary Space: O(m)