Minimum time required to reach a given score

0 0 9 minutes read

Given an integer target and an array arr[] consisting of N positive integers where arr[i] denotes the time required to score 1 point for the i^th array element, the task is to find the minimum time required to obtain the score target from the given array.

Examples:

Input: arr[] = {1, 3, 3, 4}, target = 10
Output: 6
Explanation:
At time instant, t = 1: Score of the array: {1, 0, 0, 0}
At time instant, t = 2: Score of the array: {2, 0, 0, 0}
At time instant, t = 3: Score of the array: {3, 1, 1, 0}
At time instant, t = 4: Score of the array: {4, 1, 1, 1}
At time instant, t = 5: Score of the array: {5, 1, 1, 1}
At time instant, t = 6: Score of the array: {6, 2, 2, 1}
Total score of the array after t = 5 = 6 + 2 + 2 + 1 = 11 ( > 10). Therefore, the

Input: arr[] = {2, 4, 3}, target = 20
Output: 20

Approach: The idea is to use Hashing to store the frequency of array elements and iterate over the Hashmap and keep updating the score until it reaches target. An important observation is that any element, arr[i] adds t / arr[i] to the score at any time instant t. Follow the steps below to solve the problem:

Initialize a variable, say time, to store the minimum time required and sum with 0 to store the score at any time instant t.
Store the frequency of array elements in a Hashmap M.
Iterate until the sum is less than target and perform the following steps:
- Set sum to 0 and increment the value of time by 1.
- Now, traverse the hashmap M and increment the value of sum by frequency * (time / value) in each iteration.
After completing the above steps, print the value of time as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum time
// required to achieve given score target
void findMinimumTime(int* p, int n,
                     int target)
{
    // Store the frequency of elements
    unordered_map<int, int> um;
 
    // Traverse the array p[]
    for (int i = 0; i < n; i++) {
 
        // Update the frequency
        um[p[i]]++;
    }
 
    // Stores the minimum time required
    int time = 0;
 
    // Store the current score
    // at any time instant t
    int sum = 0;
 
    // Iterate until sum is at
    // least equal to target
    while (sum < target) {
 
        sum = 0;
 
        // Increment time with
        // every iteration
        time++;
 
        // Traverse the map
        for (auto& it : um) {
 
            // Increment the points
            sum += it.second
                   * (time / it.first);
        }
    }
 
    // Print the time required
    cout << time;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 3, 3, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int target = 10;
 
    // Function Call
    findMinimumTime(arr, N, target);
 
    return 0;
}

Java

// Java program for the above approach 
import java.util.*;
import java.io.*;
  
class GFG{ 
      
// Function to calculate minimum time
// required to achieve given score target
static void findMinimumTime(int [] p, int n,
                            int target)
{
      
    // Store the frequency of elements
    HashMap<Integer,
            Integer> um = new HashMap<>();
                                          
    // Traverse the array p[]
    for(int i = 0; i < n; i++)
    {
          
        // Update the frequency
        if (!um.containsKey(p[i]))
            um.put(p[i], 1);
        else
            um.put(p[i], 
            um.get(p[i]) + 1);
    }
  
    // Stores the minimum time required
    int time = 0;
  
    // Store the current score
    // at any time instant t
    int sum = 0;
      
    while (sum < target) 
    {
        sum = 0;
          
        // Increment time with
        // every iteration
        time++;
  
        // Traverse the map
        for(Map.Entry<Integer,
                 Integer> it : um.entrySet()) 
        {
              
            // Increment the points
            sum += it.getValue() * (time / it.getKey());
        }
    }
  
    // Print the time required
    System.out.println(time); 
} 
 
// Driver Code 
public static void main(String args[]) 
{ 
    int[] arr = { 1, 3, 3, 4 };
    int N = arr.length;
    int target = 10;
      
    // Function Call
    findMinimumTime(arr, N, target);
} 
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python3 program for the above approach
 
# Function to calculate minimum time
# required to achieve given score target
def findMinimumTime(p, n, target):
     
    # Store the frequency of elements
    um = {}
 
    # Traverse the array p[]
    for i in range(n):
 
        # Update the frequency
        um[p[i]] = um.get(p[i], 0) + 1
 
    # Stores the minimum time required
    time = 0
 
    # Store the current score
    # at any time instant t
    sum = 0
 
    # Iterate until sum is at
    # least equal to target
    while (sum < target):
 
        sum = 0
 
        # Increment time with
        # every iteration
        time += 1
 
        # Traverse the map
        for it in um:
 
            # Increment the points
            sum += um[it] * (time // it)
 
    # Print time required
    print(time)
 
# Driver Code 
if __name__ == '__main__':
    arr = [1, 3, 3, 4]
    N = len(arr)
    target = 10
 
    # Function Call
    findMinimumTime(arr, N, target)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System.Collections.Generic; 
using System; 
using System.Linq;
 
class GFG{
 
// Function to calculate minimum time
// required to achieve given score target
static void findMinimumTime(int [] p, int n,
                            int target)
{
     
    // Store the frequency of elements
    Dictionary<int, 
               int> um = new Dictionary<int,
                                        int>();
                                         
    // Traverse the array p[]
    for(int i = 0; i < n; i++)
    {
         
        // Update the frequency
        if (um.ContainsKey(p[i]) == true)
            um[p[i]] += 1;
        else
            um[p[i]] = 1;
    }
 
    // Stores the minimum time required
    int time = 0;
 
    // Store the current score
    // at any time instant t
    int sum = 0;
 
    // Iterate until sum is at
    // least equal to target
    var val = um.Keys.ToList();
     
    while (sum < target) 
    {
        sum = 0;
         
        // Increment time with
        // every iteration
        time++;
 
        // Traverse the map
        foreach(var key in val) 
        {
             
            // Increment the points
            sum += um[key] * (time / key);
        }
    }
 
    // Print the time required
    Console.WriteLine(time); 
}
 
// Driver Code
public static void Main() 
{
    int []arr = { 1, 3, 3, 4 };
    int N = arr.Length;
    int target = 10;
     
    // Function Call
    findMinimumTime(arr, N, target);
}
}
 
// This code is contributed by Stream_Cipher

Javascript

<script>
 
// Js program for the above approach
// Function to calculate minimum time
// required to achieve given score target
function findMinimumTime( p,  n,
                      target)
{
    // Store the frequency of elements
    let um = new Map();
 
    // Traverse the array p[]
    for (let i = 0; i < n; i++) {
 
        // Update the frequency
        if(um[p[i]])
        um[p[i]]++;
        else
        um[p[i]] = 1
    }
 
    // Stores the minimum time required
    let time = 0;
 
    // Store the current score
    // at any time instant t
    let sum = 0;
 
    // Iterate until sum is at
    // least equal to target
    while (sum < target) {
 
        sum = 0;
 
        // Increment time with
        // every iteration
        time++;
 
        // Traverse the map
        for (let it in um) {
 
            // Increment the points
            sum += um[it]
                   * Math.floor(time / it);
        }
    }
 
    // Print the time required
    document.write(time);
}
 
// Driver Code
let arr =  [1, 3, 3, 4];
    let N = arr.length;
    let target = 10;
 
    // Function Call
    findMinimumTime(arr, N, target);
 
// This code is contributed by rohitsingh07052.
</script>

Output

Time Complexity- 0(target*N)
Auxiliary Space- 0(N)

Optimised Approach:

If we use binary search here for l=1 to h=target until we find the minimum time for which we reach the target score for time t the target score is a[0]/t+a[1]/t+….. if it is greater than equal to target then this time is possible.

C++

#include <iostream>
using namespace std;
bool possible(int arr[],int n,int target,int mid){
  int sum=0;
   
  for(int i=0;i<n;i++)
  {
    sum+=mid/arr[i];
    if(sum>=target) return true;
  }
   
  return false;
   
}
int solve(int arr[],int target,int n)
{
  int l=1;
  int h=target;
  int ans=0;
  while(l<=h)
  {
    int mid=l+(h-l)/2;
    if(possible(arr,n,target,mid))
    {
      ans=mid;
      h=mid-1;
    }
    else
      l=mid+1;
  }
   
  return ans;
}
int main() {
 
    int arr[]={1,3,3,4};
    int target=10;
    int n=sizeof(arr)/sizeof(arr[0]);
    cout<<solve(arr,target,n)<<endl;
    return 0;
}

Java

public class Main {
    public static boolean possible(int[] arr, int n, int target, int mid) {
        /*
        Returns true if it's possible to get at least 'target' 
        elements from the 'arr' array
        using a division of 'mid', false otherwise.
        */
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += mid / arr[i];
            if (sum >= target) {
                return true;
            }
        }
        return false;
    }
 
    public static int solve(int[] arr, int target, int n) {
        /*
        Finds the largest integer 'ans' such that 
        it's possible to get at least 'target' elements
        from the 'arr' array using a division of 'ans'.
        */
        int l = 1;
        int h = target;
        int ans = 0;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            if (possible(arr, n, target, mid)) {
                ans = mid;
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 4};
        int target = 10;
        int n = arr.length;
        System.out.println(solve(arr, target, n));
    }
}

Python3

def possible(arr, n, target, mid):
    """
    Returns True if it's possible to get at least 'target' elements from the 'arr' array
    using a division of 'mid', False otherwise.
    """
    sum = 0
    for i in range(n):
        sum += mid // arr[i]
        if sum >= target:
            return True
    return False
 
def solve(arr, target, n):
    """
    Finds the largest integer 'ans' such that it's possible to get at least 'target' elements
    from the 'arr' array using a division of 'ans'.
    """
    l = 1
    h = target
    ans = 0
    while l <= h:
        mid = l + (h - l) // 2
        if possible(arr, n, target, mid):
            ans = mid
            h = mid - 1
        else:
            l = mid + 1
    return ans
 
if __name__ == "__main__":
    arr = [1, 3, 3, 4]
    target = 10
    n = len(arr)
    print(solve(arr, target, n))

C#

using System;
 
class GFG {
    public static bool Possible(int[] arr, int n,
                                int target, int mid)
    {
              /*
        Returns true if it's possible to get at least 'target' 
        elements from the 'arr' array
        using a division of 'mid', false otherwise.
        */
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += mid / arr[i];
            if (sum >= target)
                return true;
        }
 
        return false;
    }
 
    public static int Solve(int[] arr, int target, int n)
    {
      /*
        Finds the largest integer 'ans' such that 
        it's possible to get at least 'target' elements
        from the 'arr' array using a division of 'ans'.
        */
        int l = 1;
        int h = target;
        int ans = 0;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            if (Possible(arr, n, target, mid)) {
                ans = mid;
                h = mid - 1;
            }
            else
                l = mid + 1;
        }
 
        return ans;
    }
 
    static void Main(string[] args)
    {
        int[] arr = { 1, 3, 3, 4 };
        int target = 10;
        int n = arr.Length;
        Console.WriteLine(Solve(arr, target, n));
    }
}
// This code is contributed by sarojmcy2e

Javascript

// js code
 
function possible(arr, n, target, mid) 
{
 
    // Returns True if it's possible to get at least
    // 'target' elements from the 'arr' array 
    // using a division of 'mid', False otherwise.
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += Math.floor(mid / arr[i]);
        if (sum >= target) {
            return true;
        }
    }
    return false;
}
 
function solve(arr, target, n)
{
 
    // Finds the largest integer 'ans' such that 
    // it's possible to get at least 'target' elements 
    // from the 'arr' array using a division of 'ans'.
    let l = 1;
    let h = target;
    let ans = 0;
    while (l <= h) {
        let mid = l + Math.floor((h - l) / 2);
        if (possible(arr, n, target, mid)) {
            ans = mid;
            h = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}
 
let arr = [1, 3, 3, 4];
let target = 10;
let n = arr.length;
console.log(solve(arr, target, n)); // 8

Output

Time Complexity: O(log(target)*N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!