Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 28, 2022 by Ria Pathak

Greedy algorithm

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()
{
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')
else if (arr.charAt(i) == '0')
}
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.