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

Answer:

The written program is in the explanation

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

}

}