AF
HomeTagSubmit NotesAsk AnythingLoginSubscribe Us
AF
1. Feel Free to ask and submit anything on Anyforum.in and get satisfactory answer
2. Registration is not compulsory, you can directly login via google or facebook
3. Our Experts are looking for yours ?.



programming-basics: Program to help the king to save the kingdom

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.

programming x 167
basics x 170
Posted On : 2017-10-07 16:47:24.0
profile Divesh - anyforum.in Divesh
102180
up-rate
5
down-rate

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;
}

Posted On : 2017-10-09 23:52:31
Satisfied : 11 Yes  16 No
profile Rishi Kumar - anyforum.in Rishi Kumar
523187021168
Reply This Thread
up-rate
4
down-rate
Comments
Please remove your answer this contest is going on. It breaks the spirit.
Thanks.
profile Kush - anyforum.in Kush
0  0  0
Posted On :2017-10-10 01:52:48.0
Leave a Comment
program giving error ..please give the output also
profile Mj Alive - anyforum.in Mj Alive
0  0  0
Posted On :2017-10-11 10:12:12.0
Leave a Comment
Hi Alive,
Please let me know what error you are facing.
profile Rishi Kumar - anyforum.in Rishi Kumar
523  1870  21168
Posted On :2017-10-11 19:34:37.0
Leave a Comment
hey bro,
I am testing your code 3 test failed while compiling it.
can you please check complexity of that?
profile Suraj Yadav - anyforum.in Suraj Yadav
0  0  0
Posted On :2017-10-17 21:44:21.0
Leave a Comment
i want this program in C language.
profile mohanram m - anyforum.in mohanram m
0  0  0
Posted On :2017-10-17 21:45:47.0
Leave a Comment
Hi Suraj,
Please give me test data for which it failed. I´ll check.
profile Rishi Kumar - anyforum.in Rishi Kumar
523  1870  21168
Posted On :2017-10-17 22:20:16.0
Leave a Comment

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;
}

Posted On : 2017-10-10 10:44:40
Satisfied : 9 Yes  11 No
profile Garima Gupta - anyforum.in Garima Gupta
596129025113
Reply This Thread
up-rate
5
down-rate
Comments
Hi Garima,
It´s been edited now.

Thanks,
Rishi
profile Rishi Kumar - anyforum.in Rishi Kumar
523  1870  21168
Posted On :2017-10-10 21:47:20.0
Leave a Comment

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

Posted On : 2017-10-22 21:34:40
Satisfied : 0 Yes  0 No
profile vikash kumar - anyforum.in vikash kumar
0-50
Reply This Thread
up-rate
-5
down-rate
Comments
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");
}
}
profile Garima Gupta - anyforum.in Garima Gupta
596  1290  25113
Posted On :2017-10-23 23:10:20.0
Leave a Comment

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 ./.

Posted On : 2017-10-23 10:49:36
Satisfied : 0 Yes  0 No
profile kavi - anyforum.in kavi
0-40
Reply This Thread
up-rate
-4
down-rate
Comments
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.
profile Garima Gupta - anyforum.in Garima Gupta
596  1290  25113
Posted On :2017-10-23 23:19:32.0
Leave a Comment



Post Answer
Please Login First to Post Answer: Login login with facebook - anyforum.in