Find the index with minimum score from a given array

0 0 4 minutes read

Given an array A[] of size N(1 ? N ? 10⁵), consisting of positive integers, where the score of an index i in range [0, N – 1] is defined as:

Score[i] = A[i] * ((i + A[i] < N) ? Score(i + A[i]) : 1)

The task is to find the index with minimum score.

Examples:

Input: A[] = {1, 2, 3, 4, 5}
Output: 2
Explanation:

Score[4] = 5 * 1 = 5

Score[3]. = 4 * 1 = 4

Score[2] = 3 * 1 = 3 (Minimum)

Score[1] = 2 * Score[3] = 2 * 4 = 8

Score[0] = 1 * Score[1] = 1 * 8 = 8

Input: A[] = {9, 8, 1, 2, 3, 6}
Output : 4

Approach: Follow the steps below to solve the problem

Traverse the array in reverse, i.e. iterate from i = N – 1 to 0.
For every i, check if (A[i] + i) is less than N or not.
Update score[i] for index i as Score[i] = A[i] * ((i + A[i] < N) ? Score(i + A[i]) ? 1)
Print the index with minimum score.

Below is the implementation of above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
 
using namespace std;
 
 
//Function to find the index
//with minimum score
void Min_Score_Index(int N, vector<int> A){
 
    //Stores the score of current index
    vector<int> Score(N,0);
 
    //Traverse the array in reverse
    for (int i=N-1;i>=0;i--){
 
        if (A[i] + i < N)
            Score[i] = A[i] * Score[A[i] + i];
        else
            Score[i] = A[i];
    }
 
    //Update minimum score
    int min_value = INT_MAX;
 
    for(int i:Score) min_value = min(i,min_value);
 
    //Print the index with minimum score
    int ind = 0;
 
    for(int i=0;i<N;i++){
      if(Score[i]==min_value) ind = i;
    }
 
    cout<<(ind);
}
 
 
 
//Driver Code
int main(){
  int N = 5;
  vector<int> A ={1, 2, 3, 4, 5};
 
  Min_Score_Index(N, A);
 
}

Java

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function to find the index
// with minimum score
static void Min_Score_Index(int N, int []A)
{
 
    // Stores the score of current index
    int []Score = new int[N];
 
    // Traverse the array in reverse
    for (int i = N - 1; i >= 0; i--)
    {
 
        if (A[i] + i < N)
            Score[i] = A[i] * Score[A[i] + i];
        else
            Score[i] = A[i];
    }
 
    // Update minimum score
    int min_value = Integer.MAX_VALUE; 
    for(int i:Score) min_value = Math.min(i, min_value);
 
    // Print the index with minimum score
    int ind = 0;
    for(int i = 0; i < N; i++)
    {
      if(Score[i] == min_value)
        ind = i;
    }
    System.out.print(ind);
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 5;
  int []A ={1, 2, 3, 4, 5};
  Min_Score_Index(N, A);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
 
# Function to find the index
# with minimum score
def Min_Score_Index(N, A):
 
    # Stores the score of current index
    Score = [0] * N
 
    # Traverse the array in reverse
    for i in range(N - 1, -1, -1):
        if A[i] + i < N:
            Score[i] = A[i] * Score[A[i] + i]
        else:
            Score[i] = A[i]
 
    # Update minimum score
    min_value = min(Score)
 
    # Print the index with minimum score
    ind = Score.index(min_value)
    print(ind)
 
# Driver Code
if __name__ == "__main__":
    N = 5
    A = [1, 2, 3, 4, 5]
    Min_Score_Index(N, A)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find the index
// with minimum score
static void Min_Score_Index(int N, int[] A)
{
     
    // Stores the score of current index
    int[] Score = new int[N];
 
    // Traverse the array in reverse
    for(int i = N - 1; i >= 0; i--) 
    {
        if (A[i] + i < N)
            Score[i] = A[i] * Score[A[i] + i];
        else
            Score[i] = A[i];
    }
 
    // Update minimum score
    int min_value = Int32.MaxValue;
    foreach(int i in Score) 
    {
        min_value = Math.Min(i, min_value);
    }
 
    // Print the index with minimum score
    int ind = 0;
    for(int i = 0; i < N; i++) 
    {
        if (Score[i] == min_value)
            ind = i;
    }
    Console.WriteLine(ind);
}
 
// Driver Code
public static void Main()
{
    int N = 5;
    int[] A = { 1, 2, 3, 4, 5 };
     
    Min_Score_Index(N, A);
}
}
 
// This code is contributed by chitranayal

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find the index
// with minimum score
function Min_Score_Index(N, A){
 
    // Stores the score of current index
    var Score = Array(N).fill(0);
 
    // Traverse the array in reverse
    for (var i=N-1;i>=0;i--){
 
        if (A[i] + i < N)
            Score[i] = A[i] * Score[A[i] + i];
        else
            Score[i] = A[i];
    }
 
    // Update minimum score
    var min_value = 1000000000;
 
    Score.forEach(i => {
        min_value = Math.min(i,min_value); 
    });
 
    // Print the index with minimum score
    var ind = 0;
 
    for(var i=0;i<N;i++){
      if(Score[i]==min_value) ind = i;
    }
 
    document.write(ind);
}
 
 
 
// Driver Code
 
var N = 5;
var A =[1, 2, 3, 4, 5];
Min_Score_Index(N, A);
 
</script>

Output:

Time Complexity: O(N)
Auxiliary Space: O(N)

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!