Last Updated on March 28, 2022 by Ria Pathak

### CONCEPTS USED:

Greedy algorithm

### DIFFICULTY LEVEL:

Medium.

### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Arnab has made a team and he wants to fight with another team with some modified form of Kabaddi. In this game, all the players stand in a line. Now in a turn Arnab’s team member can hold and win over an player of opposite team upto K distance apart. Each player of Arnab’s team can win over only one opponent player and upto K distance. Player of Arnab’s team is marked by 1 and opponents team is marked by 0.Find the maximum number of people Arnab’s team can win over.

**See original problem statement here**

#### For Example :

```
1
101001 3
3
First player can win over 2nd player,3rd player can win over 4th player and last player can win over 2nd last player.
```

### OBSERVATION:

The maximum number of defeated players increases if each player from Arnab’s team deats the nearest player from opponent team.

For example, in the given test case player 1 should first try for nearest index lesser than k.

### SOLVING APPROACH:

Let us see if we can apply greedy algorithm to this problem.

A problem can be solved with greedy approch ,if it satisfies:

Greedy choice property: A global (overall) optimal solution can be reached by choosing the optimal choice at each step.

Optimal substructure: A problem has an optimal substructure if an optimal solution to the entire problem contains the optimal solutions to the sub-problems.Since it satisfies both the properties, we can apply greedy here.

## BRUTE FORCE:

Initialize a counter to 0.

Iterate through each index and loop if the current index contains 1.

The loop runs from (i-k) or 0 (whichever is maximum) to i+k or n-1 (whichever is minimum).

if the character at looped index in the given string is 0.increase the counter by 1.

#include <bits/stdc++.h> using namespace std; int main() { //write your code here int t;cin>>t; while(t--) { string s;int k; cin>>s>>k; int n=s.length(); int count=0; for(int i=0;i<s.length();i++) {if(s[i]=='1') {for(int j=max(0,i-k);j<=min(n-1,i+k);j++) { if(s[j]=='0') { count++; s[j]=-1; break; } }} } cout<<count<<"\n"; } return 0; }

#### EFFICIENT SOLUTION:

Make two separate vectors each for 0 and 1.

Store the index of all 1s in one vector and 0s in the other.

Initiaze count to 0.

Simultaneously traverse both the vectors.

#include <stdio.h> #include<stdlib.h> #include<string.h> int solve(char arr[], int n, int k) { int res = 0; int thi[n]; int pol[n];int x=0,j=0; for (int i = 0; i < n; i++) { if (arr[i] == '1') pol[x++]=i; else if (arr[i] == '0') thi[j++]=i; } int l = 0, r = 0; while (l < x && r < j) { if (abs(thi[l] - pol[r]) <= k) { res++; l++; r++; } else if (thi[l] < pol[r]) l++; else r++; } return res; } int main() { int t; scanf("%d",&t); while(t--) { char s[1005]; int k; scanf("%s",s); scanf("%d",&k); printf("%d\n",solve(s,strlen(s),k)); } return 0; }

#include <bits/stdc++.h> using namespace std; int solve(string arr, int n, int k) { int res = 0; vector<int> thi; vector<int> pol; for (int i = 0; i < n; i++) { if (arr[i] == '1') pol.push_back(i); else if (arr[i] == '0') thi.push_back(i); } int l = 0, r = 0; while (l < thi.size() && r < pol.size()) { if (abs(thi[l] - pol[r]) <= k) { res++; l++; r++; } else if (thi[l] < pol[r]) l++; else r++; } return res; } int main() { int t; cin>>t; while(t--) { string s; int k; cin>>s>>k; cout<<solve(s,s.length(),k)<<endl;; } return 0; }

import java.util.*; class Solution{ static int solve(String arr, int n, int k) { int res = 0; ArrayList<Integer> thi=new ArrayList<>(); ArrayList<Integer> pol=new ArrayList<>();; for (int i = 0; i < n; i++) { if (arr.charAt(i) == '1') pol.add(i); else if (arr.charAt(i) == '0') thi.add(i); } int l = 0, r = 0; while (l < thi.size() && r < pol.size()) { if (Math.abs(thi.get(l) - pol.get(r)) <= k) { res++; l++; r++; } else if (thi.get(l) < pol.get(r)) l++; else r++; } return res; } public static void main (String[] args) { Scanner sc=new Scanner(System.in); int t=sc.nextInt(); while(t-->0) { String s=sc.next(); int k=sc.nextInt(); System.out.println(solve(s,s.length(),k)); } } }

[forminator_quiz id="1427"]

This article tried to discuss **Greedy algorithm**. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm you can check out MYCODE | Competitive Programming.