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 operationint 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 codeint 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 operationdef 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 codearr = [31, 12, 25, 27, 32, 19]K = 5N = 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> |
4
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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
