Problem Statement:
There are N cities in a kingdom. These cities are aligned in a row. So, each city has two neighbours except first and last city. Each city has an F-number which denotes the maximum cities he can ask for help in case of an attack. Each F-number lies between 1 to N. Two cities cannot have same F-number. The Power of a city c is the sum of F-numbers of the cities that c asked for help. In case of an attack, to save time, representative of the city will go to the first city he wants help from and ask the city to propogate the message to its right neighbour. Right neighbour will propagate the message to its right neighbour and so on. This process will stop when the attacked city gets the help form as many cities as it wants. It is obvious that a city will try to get maximum power.
Now a neighbour kingdom with a collective power K has attacked the kingdom. In this attack a city will survive if its power is greater than the power of the attacking kingdom(K) otherwise the city will be destroyed. Now the king wants to prepare a plan to protect the kingdom from this threat. So he hired you. King wants to know which city with minimum F-number can survive. So help the king to save the kingdom.
INPUT SPECIFICATION
Your function contains two arguments- An integer K denoting the collective power of the attacking kingdom and an One dimensional Integer array of Size N in which ith element denotes the F-number of the ith city.
First line of input contains an Integer K.(1<=K<=10^12)
Second line of input contains an Integer N denoting the size of Array. (1<=N<=10^5)
Next N lines of input contains a single integer from 1 to N.
OUTPUT SPECIFICATION
You must return an integer- minimum F-number of the cities that can survive. Return -1 if no city can survive.
EXAMPLES
Sample Test Case 1-
Input
5
3
1
2
3
Output
3
Explanation
maximum power of the cities will be as following-
1st city- max(1,2,3)=3
2nd city- max((1+2),(2+3))=max(3,5)=5
3rd city- 6
Power of the first two cities is less than or equal to the collective power of the attacking kingdom(5). So, Both these cities will be destroyed. Only city remaining will be 3rd city.

5

Answers
Please check below code as per my understanding. Please test it with more test cases. In case of any query, keep your comments posted on this thread.
*[Edited after Second answer from Garima]
//input 1 is the attacked power referred as K and input2 refers to the array of cities
public static int saveKingdom(int input1,int[] input2){
int max=0;
int result=-1;
int[] citiesArray=Arrays.copyOf(input2, input2.length);
Arrays.sort(citiesArray);
for(int F:citiesArray){
max=getMax(input2, F);
if(max>input1){
result=F;
break;
}
}
return result;
}
public static int getMax(int[] array,int number){
int count=0;
int max=0;
int tempMax=0;
int j=0;
for(int i=0;i<array.length;i++){
j=i;
count=0;
tempMax=0;
//checks the maximum possible power for respective combination number
while(count<number && j<array.length){
tempMax=tempMax+array[j];
if(tempMax>max)
max=tempMax;
count++;
j++;
}
//checks it reached to last city, no further iterations are required.
if(j==array.length)
break;
}
return max;
}

4

Please remove your answer this contest is going on. It breaks the spirit.
Thanks.

program giving error ..please give the output also

Hi Alive,
Please let me know what error you are facing.

hey bro,
I am testing your code 3 test failed while compiling it.
can you please check complexity of that?

i want this program in C language.

Hi Suraj,
Please give me test data for which it failed. I´ll check.

Just wants to add something in above code to make it better. In saveKingdom method traverse the node in ascending order of F-number as we need to find minimum F-Number.
public static int saveKingdom(int attackedPower,int[] cities){
int max=0;
int result=-1;
int[] citiesArray=Arrays.copyOf(cities, cities.length);
Arrays.sort(citiesArray);
for(int F:citiesArray){
max=getMax(cities, F);
if(max>attackedPower){
result=F;
break;
}
}
return result;
}

5

Hi Garima,
It´s been edited now.
Thanks,
Rishi

Hi,
plase help me....main method will not define so how can define main method.

-5

Hi,
you can put main method as below. Don´t forget to add the import statements for Scanner class as import java.util.Scanner;
public static void main(String[] args) throws Exception{
Scanner input=new Scanner(System.in);
int K=input.nextInt();
int N=input.nextInt();
if(1<=K && K<=Math.pow(10,12) && 1<=N && N<=Math.pow(10, 5)){
int[] cities=new int[N];
for(int i=0;i<N;i++){
cities[i]=input.nextInt();
}
System.out.println(saveKingdom(K, cities));
}else{
throw new Exception("Invalid Inputs");
}
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class CandidateCode {
/*
* Complete the function below.
*/
public static int fnumber(long input1,int[] input2)
{
int max=0;
int result=-1;
int[]cities=Arrays.copyOf(input2,input2.length);
Arrays.sort(input2array);
for(int F:input2Array){
max=getMax(input2,F);
if(max>input1){
result=-F;
break;
}
}
return result;
}
public static int getMax(int[] array,int number){
// Scanner in = new Scanner(System.in);
int count=0;
int max=0;
int tempMax=0;
int j=0;
for(int i=0;i<array.length;i++){
j=i;
count=0;
tempMax=0;
while(count<number && j<array.length){
tempMax=tempMax+array[j];
if(tempMax>max)
max=tempMax;
count++;
j++;
}
if(j==array.length)
break;
}
return max;
}
public static void main(String[] args) throws IOException{
Scanner in = new Scanner(System.in);
int output = 0;
long ip1 = Long.parseLong(in.nextLine().trim());
int ip2_size = 0;
ip2_size = Integer.parseInt(in.nextLine().trim());
int[] ip2 = new int[ip2_size];
int ip2_item;
for(int ip2_i = 0; ip2_i < ip2_size; ip2_i++) {
ip2_item = Integer.parseInt(in.nextLine().trim());
ip2[ip2_i] = ip2_item;
}
output = fnumber(ip1,ip2);
System.out.println(String.valueOf(output));
}
}
Compilation error #stdin compilation error #stdout 0s 0KB comments (0)
stdin copy
Standard input is empty
compilation info
Main.java:6: error: class CandidateCode is public, should be declared in a file named CandidateCode.java
public class CandidateCode {
^
Main.java:16: error: cannot find symbol
Arrays.sort(input2array);
^
symbol: variable input2array
location: class CandidateCode
Main.java:17: error: cannot find symbol
for(int F:input2Array){
^
symbol: variable input2Array
location: class CandidateCode
3 errorscan any1 tel me d crt ans ./.

-4

Hi kavi,
I think you are trying to run the program online. Few things i can tell you like
* replace the content of fnumber method by saveKingdom method as shown in first answer.
* add some import statements for Arrays class.
* remove public from your class name.