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

Popular posts from this blog

4.Sort an array of 0's, 1's & 2's.

1. Reverse

3. Height of Binary tree