Question

You will be given a value of n and k, one line each. You will write a program that determines the minimum number of probe attempts in the worst case before you determine the correct day. Your output should be a single number that represents the minimum number of probes.

Answer 1

The written program is in the explanation

Step-by-step explanation:

RomanticDays.java

import java.util.Scanner;

class RomanticDays {

static int max(int a, int b) {

return (a > b) ? a : b; }

static int minAttempt(int k, int n) {

int romancticDays[][] = new int[k+1][n+1];

int res;

int loop1,loop2,i;

for (loop1 = 1; loop1 <= k; loop1++) {

romancticDays[loop1][1] = 1;

romancticDays[loop1][0] = 0; }

for (loop2 = 1; loop2 <= n; loop2++)

romancticDays[1][loop2] = loop2;

for (loop1 = 2; loop1 <= k; loop1++) {

for (loop2 = 2; loop2 <= n; loop2++) {

romancticDays[loop1][loop2] = Integer.MAX_VALUE;

for (i = 1; i <= loop2; i++) {

res = 1 + max(romancticDays[loop1 - 1][i - 1], romancticDays[loop1][loop2 - i]);

if (res < romancticDays[loop1][loop2])

romancticDays[loop1][loop2] = res;

}

}

}

return romancticDays[k][n];

}

/* Driver program to test */

public static void main(String args[]) {

int n,k;

System.out.print("Enter the value of N and k :");

Scanner sc=new Scanner(System.in);

n=sc.nextInt();

k=sc.nextInt();

System.out.println( minAttempt(k,n));

}

}