3
\$\begingroup\$

I am writing code for the challenge given here . Below the text:

Each time Sunny and Johnny take a trip to the Ice Cream Parlor, they pool their money to buy ice cream. On any given day, the parlor offers a line of flavors. Each flavor has a cost associated with it. Given the value of and the of each flavor for trips to the Ice Cream Parlor, help Sunny and Johnny choose two distinct flavors such that they spend their entire pool of money during each visit. ID numbers are the 1- based index number associated with a cost. For each trip to the parlor, print the ID numbers for the two types of ice cream that Sunny and Johnny purchase as two space-separated integers on a new line. You must print the smaller ID first and the larger ID second.

For example, there are flavors having cost = [2, 1, 3, 5, 6]. Together they have money = 5 to spend. They would purchase flavor ID's 1 and 3 for a cost of 2 + 3 = 5 . Use 1 based indexing for your response.

I have written code for the problem. However, it is running for most of the test cases except three. The error message that they show is that "Your code did not execute within the time limits". Apparently the code needs to be optimized. Can anyone please tell how may I do that?

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class Solution {

    // Complete the whatFlavors function below.
    static void whatFlavors(int[] cost, int money) {

         int baseItem=0, comparedItem = 0,totalAmount=0, chosenFlavour1=0,
                chosenFlavour2=0,flag=0;
        for(int i = 0 ; i<(cost.length-1); i++)
        {
            baseItem = cost[i];
            for(int j = (i+1); j< (cost.length);j++)
            {
                comparedItem= cost[j];
                totalAmount = baseItem + comparedItem;

                if(totalAmount == money)
                {
                    chosenFlavour1 = i;
                    chosenFlavour2 = j;
                    flag = 1;
                    break;
                }

            }

            if(flag == 1)
            {
               break; 
            }
        }

        chosenFlavour1++;
        chosenFlavour2++;
        System.out.println(chosenFlavour1+" "+chosenFlavour2);


    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int tItr = 0; tItr < t; tItr++) {
            int money = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int n = scanner.nextInt();
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            int[] cost = new int[n];

            String[] costItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

            for (int i = 0; i < n; i++) {
                int costItem = Integer.parseInt(costItems[i]);
                cost[i] = costItem;
            }

            whatFlavors(cost, money);
        }

        scanner.close();
    }
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Hint: this problem is in the Hash Map section. \$\endgroup\$ – vnp Apr 24 '20 at 19:01
2
\$\begingroup\$

Your algorithm is slow in some cases because of the time complexity O(n^2). (starting the second loop from i+1 makes it twice faster than starting from 0, but it doesn't change the time complexity which has much greater impact on performance)

To improve your time complexity you need to reduce the amount of times you look at items in the array. One way of doing it is by first sorting it (more precisely, sorting index-value pairs to keep record of the original indexing) and then iterating over the sorted array once (O(n)) while taking advantage of the fact that it is sorted. I'll leave you the task of learning about integer sorting algorithms (of time complexity O(n log n)), and only explain how to use the sorted array to find the final answer.

You can look at both edges of the array (smallest and biggest number), if their sum is too small you can increase it by advancing the lower-edge index to look at a bigger number, and if the sum is too big you can decrease it by advancing the higher-edge index to look at a smaller number. Repeat it until you reach the needed sum, then get the original indices and increment them to get the IDs you need for the output.

As @vnp hinted, there is a better solution than mine (with time complexity O(n)) using a hash table.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It is a bit simplistic. After sorting, the original indexing is lost. You need to sort cost, index tuples. \$\endgroup\$ – vnp Apr 24 '20 at 18:56
  • \$\begingroup\$ @vnp good point, thanks for pointing it out! \$\endgroup\$ – potato Apr 24 '20 at 19:02
2
\$\begingroup\$

As @vnp's comments suggested, the solution requires the use of a Map to store the cost, index tuples. Substantially you have to iterate over your costs array and for every cost element check if one key in your map satisfies the condition key = money - cost. If the condition is satisfied you will print the two indexes, otherwise you will add the touple cost, index to your map. Below my code that passed all hackerrank tests:

public static void whatFlavors(int[] costs, int money) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < costs.length; ++i) {
        int index = i + 1;
        int cost = costs[i];
        int key = money - cost;
        if (map.containsKey(key)) {
            System.out.format("%d %d\n", map.get(key), index);
            return;
        }
        map.put(cost, index);
    }
}

I would have prefer to have a function returning the two indexes array and print them outside in the main program, but as expected any modification of the function signature will fail the tests.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.