19. Bishu and Soldiers
19. Bishu and Soldiers
Problem link :- click here
package program;
import java.util.Arrays;
class Bishu
{
int n;
int sum_of_power;
Bishu()
{}
Bishu(int a, int b)
{
this.n = a;
this.sum_of_power = b;
}
}
public class Searching__19
{
/*
Bishu went to fight for Coding Club. There were N soldiers with various powers.
There will be Q rounds to fight and in each round, Bishu's power will be varied.
With power M Bishu can kill all the soldiers with power less than or equal to M.
After each round, all the soldiers who are dead in the previous round will reborn.
Such that in each round there will be N soldiers to fight. As Bishu is weak in
Mathematics, help him to count the number of soldiers that he can kill in each
round and the total sum of their powers.
pow_of_sol[] = {1, 2, 3, 4, 5, 6, 7} pow_of_bishu[] = {3, 10, 2}
output : 3 6
7 28
2 3
Since the size of the pow_of_bishu[] is 3, there are 3 rounds. therefore there
are 3 output.
I don't know the time complexity of this problem.
*/
static Bishu[] bishuAndSoldier(int pow[], int n, int bis[])
{
/*
//q is the number of rounds
int q = bis.length;
Bishu result[] = new Bishu[q];
//we will find the solution round wise
for(int k=0; k<q; k++)
{
int count = 0;
int sum = 0;
for(int i=0; i<n; i++)
{
if( bis[k] >= pow[i] )
{
count++;
sum += pow[i];
}
}
//after finding the answer in each round we will add it to the result
result[k] = new Bishu(count, sum);
}
return result;
*/
//there is a better solution than the above solution we can sort the pow[]
//and can find the upper_bound up-to who Bishu can defeat and can find
//the sum up-to that element
// TC :- O(n log(n) )
Arrays.sort(pow);
//q is number of rounds
int q = bis.length;
Bishu result[] = new Bishu[q];
for(int i=0; i<q; i++)
{
//This for loop indicates the number of rounds
// TC :- O(log n)
int low = 0;
int high = n-1;
while(low<=high)
{
int mid = (low+high)/2;
if(pow[mid] <= bis[i])
low = mid + 1;
else
high = mid -1;
}
int index = high;
//we have found the index of the element up-to which Bishu can defeat
//now we have to find the sum of the powers of the soldiers who are
//defeated TC :- O( q*(index+1) )
int sum = 0;
for(int j=0; j<=index; j++)
sum += pow[j];
result[i] = new Bishu(index+1, sum);
}
return result;
}
public static void main(String[] args)
{
int pow[] = {1, 2, 3, 4, 5, 6, 7};
int bis[] = {3, 10, 2};
Bishu ans[] = bishuAndSoldier(pow, pow.length, bis);
System.out.println("Number of soldiers defeated by Bishu and the sum of their powers :");
for(int i=0; i<ans.length; i++)
System.out.println(ans[i].n + " " + ans[i].sum_of_power);
}
}
Time complexity :- O()
Space complexity :- O()
Comments
Post a Comment