Find the index which is the last to be reduced to zero after performing a given operation

0 0 4 minutes read

Given an integer array arr[] of size N and an integer K, the task is to find the index which will be the last to be reduced to zero after performing a given operation. The operation is described as follows:

Starting from arr[0] to arr[N – 1], update each element as arr[i] = arr[i] – K.
If arr[i] < K then set arr[i] = 0 and no further operation will be performed on arr[i] once it is 0.
Repeat the above steps till all the elements are reduced to 0.

Print the index which will be the last to become zero.
Examples:

Input: arr[] = { 3, 2, 5, 7, 2, 9 }, K = 4
Output: 5
Operation 1: arr[] = {0, 0, 1, 3, 0, 5}
Operation 2: arr[] = {0, 0, 0, 0, 0, 1}
Operation 3: arr[] = {0, 0, 0, 0, 0, 0}
Index 5 is the last to reduce.
Input: arr[] = { 31, 12, 25, 27, 32, 19 }, K = 5
Output: 4

Approach: At each step the element at a particular index is subtracted by K. So, a particular element takes ceil(arr[i] / K) or (arr[i] + K – 1) / K steps to reduce to zero. So the required index is given by the array index with maximum (arr[i] + K – 1)/K value. If the maximum value is present more than once then return the largest index as the operation is performed from 0 to N – 1.
Below is the implementation of the above approach:

CPP

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns the index
// which will be the last to become
// zero after performing given operation
int findIndex(int a[], int n, int k)
{
 
    // Initialize the result
    int index = -1, max_ceil = INT_MIN;
 
    for (int i = 0; i < n; i++) {
 
        // Finding the ceil value
        // of each index
        a[i] = (a[i] + k - 1) / k;
    }
 
    for (int i = 0; i < n; i++) {
 
        // Finding the index with
        // maximum ceil value
        if (a[i] >= max_ceil) {
            max_ceil = a[i];
            index = i;
        }
    }
 
    return index;
}
 
// Driver code
int main()
{
    int arr[] = { 31, 12, 25, 27, 32, 19 };
    int K = 5;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << findIndex(arr, N, K);
 
    return 0;
}

Java

// Java implementation of the approach 
import java .io.*;
 
class GFG
{
     
    // Function that returns the index 
    // which will be the last to become 
    // zero after performing given operation 
    static int findIndex(int[] a, int n, int k) 
    { 
     
        // Initialize the result 
        int index = -1, max_ceil = Integer.MIN_VALUE; 
     
        for (int i = 0; i < n; i++) 
        { 
     
            // Finding the ceil value 
            // of each index 
            a[i] = (a[i] + k - 1) / k; 
        } 
     
        for (int i = 0; i < n; i++)
        { 
     
            // Finding the index with 
            // maximum ceil value 
            if (a[i] >= max_ceil) 
            { 
                max_ceil = a[i]; 
                index = i; 
            } 
        } 
     
        return index; 
    } 
     
    // Driver code 
    static public void main (String[] args)
    { 
        int []arr = { 31, 12, 25, 27, 32, 19 }; 
        int K = 5; 
        int N = arr.length ; 
     
        System.out.print(findIndex(arr, N, K)); 
    } 
}
 
// This code is contributed by anuj_67..

Python

# Python implementation of the approach
 
# Function that returns the index
# which will be the last to become
# zero after performing given operation
def findIndex(a, n, k):
 
    # Initialize the result
    index = -1
    max_ceil = -10**9
 
    for i in range(n):
 
        # Finding the ceil value
        # of each index
        a[i] = (a[i] + k - 1) // k
 
    for i in range(n):
 
        # Finding the index with
        # maximum ceil value
        if (a[i] >= max_ceil):
            max_ceil = a[i]
            index = i
         
 
    return index
 
# Driver code
 
arr = [31, 12, 25, 27, 32, 19]
K = 5
N = len(arr)
 
print(findIndex(arr, N, K))
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach 
using System;
 
class GFG
{
     
    // Function that returns the index 
    // which will be the last to become 
    // zero after performing given operation 
    static int findIndex(int[] a, int n, int k) 
    { 
     
        // Initialize the result 
        int index = -1, max_ceil = int.MinValue; 
     
        for (int i = 0; i < n; i++) 
        { 
     
            // Finding the ceil value 
            // of each index 
            a[i] = (a[i] + k - 1) / k; 
        } 
     
        for (int i = 0; i < n; i++)
        { 
     
            // Finding the index with 
            // maximum ceil value 
            if (a[i] >= max_ceil) 
            { 
                max_ceil = a[i]; 
                index = i; 
            } 
        } 
     
        return index; 
    } 
     
    // Driver code 
    static public void Main ()
    { 
        int []arr = { 31, 12, 25, 27, 32, 19 }; 
        int K = 5; 
        int N = arr.Length ; 
     
        Console.WriteLine(findIndex(arr, N, K)); 
    } 
}
 
// This code is contributed by AnkitRai01

Javascript

<script>
 
// javascript implementation of the approach 
 
// Function that returns the index 
// which will be the last to become 
// zero after performing given operation 
function findIndex(a, n, k) 
{ 
 
    // Initialize the result 
    var index = -1, max_ceil = Number.MIN_VALUE; 
 
    for (i = 0; i < n; i++) 
    { 
 
        // Finding the ceil value 
        // of each index 
        a[i] = (a[i] + k - 1) / k; 
    } 
 
    for (i = 0; i < n; i++)
    { 
 
        // Finding the index with 
        // maximum ceil value 
        if (a[i] >= max_ceil) 
        { 
            max_ceil = a[i]; 
            index = i; 
        } 
    } 
 
    return index; 
} 
     
// Driver code 
 
var arr = [ 31, 12, 25, 27, 32, 19 ]; 
var K = 5; 
var N = arr.length ; 
 
document.write(findIndex(arr, N, K)); 
 
// This code is contributed by Amit Katiyar 
 
</script>

Output:

Time Complexity: O(N), as we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(1), as we are not using any extra space.

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!