Find the index of the smallest element to be removed to make sum of array divisible by K

0 0 6 minutes read

Given an array arr[] of size N and a positive integer K, the task is to find the index of the smallest array element required to be removed to make the sum of remaining array divisible by K. If multiple solutions exist, then print the smallest index. Otherwise, print -1.

Examples:

Input: arr[ ] = {6, 7, 5, 1}, K = 7
Output: 2
Explanation:
Removing arr[0] from arr[] modifies arr[] to { 7, 5, 1 }. Therefore, sum = 13
Removing arr[1] from arr[] modifies arr[] to { 6, 5, 1 }. Therefore, sum = 12
Removing arr[2] from arr[] modifies arr[] to { 6, 7, 1 }. Therefore, sum = 14
Since the sum (= 14) is divisible by K(= 7), the required output is the index 2.

Input: arr[ ] = {14, 7, 8, 2, 4}, K = 7
Output: 1

Naive Approach: The simplest approach to solve this problem is to traverse the array and calculate the sum by removing the current element from the array. If the obtained sum is divisible by K, then print the current index. Otherwise, insert the removed element into the array.

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

Approach: The above approach can be optimized by precalculating the sum of the array. Finally, traverse the array and check if (sum – arr[i]) is divisible by K or not. If found to be true, then print the current index. Follow the steps below to solve the problem:

Calculate the sum of the array and store it in a variable say, sum.
Initialize two variables say, res and mini to store the index of the smallest element and the element such that removing the elements makes the sum divisible by K.
Traverse the array, and check if (sum – arr[i]) is divisible by K or not. If found to be true, then check if arr[i] is less than mini or not. If found to be true, then update mini = arr[i] and res = i.
Finally, print the res.

Below is the implementation of the above approach:

C++14

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find index of the smallest array element
// required to be removed to make sum divisible by K
int findIndex(int arr[], int n, int K)
{
 
    // Stores sum of array elements
    int sum = 0;
 
    // Stores index of the smallest element
    // removed from the array to make sum
    // divisible by K
    int res = -1;
 
    // Stores the smallest element removed
    // from the array to make sum divisible by K
    int mini = 1e9;
 
    // Traverse the array, arr[]
    for (int i = 0; i < n; i++) {
 
        // Update sum
        sum += arr[i];
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < n; i++) {
 
        // Calculate remaining sum
        int temp = sum - arr[i];
 
        // If sum is divisible by K
        if (temp % K == 0) {
 
            // If res ==-1 or mini is greater
            // than arr[i]
            if (res == -1 || mini > arr[i]) {
 
                // Update res and mini
                res = i + 1;
                mini = arr[i];
            }
        }
    }
 
    return res;
}
 
// Driver Code
int main()
{
    int arr[] = { 14, 7, 8, 2, 4 };
    int K = 7;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << findIndex(arr, N, K);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
// Function to find index of the smallest array element
// required to be removed to make sum divisible by K
static int findIndex(int arr[], int n, int K)
{
 
    // Stores sum of array elements
    int sum = 0;
 
    // Stores index of the smallest element
    // removed from the array to make sum
    // divisible by K
    int res = -1;
 
    // Stores the smallest element removed
    // from the array to make sum divisible by K
    int mini = (int) 1e9;
 
    // Traverse the array, arr[]
    for (int i = 0; i < n; i++)
    {
 
        // Update sum
        sum += arr[i];
    }
 
    // Traverse the array arr[]
    for (int i = 0; i < n; i++)
    {
 
        // Calculate remaining sum
        int temp = sum - arr[i];
 
        // If sum is divisible by K
        if (temp % K == 0)
        {
 
            // If res ==-1 or mini is greater
            // than arr[i]
            if (res == -1 || mini > arr[i])
            {
 
                // Update res and mini
                res = i + 1;
                mini = arr[i];
            }
        }
    }
    return res;
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 14, 7, 8, 2, 4 };
    int K = 7;
    int N = arr.length;
    System.out.print(findIndex(arr, N, K));
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python3 program to implement
# the above approach
 
# Function to find index of the smallest array element
# required to be removed to make sum divisible by K
def findIndex(arr, n, K) :
 
    # Stores sum of array elements
    sum = 0
 
    # Stores index of the smallest element
    # removed from the array to make sum
    # divisible by K
    res = -1
 
    # Stores the smallest element removed
    # from the array to make sum divisible by K
    mini = 1e9
 
    # Traverse the array, arr[]
    for i in range(n):
 
        # Update sum
        sum += arr[i]
 
    # Traverse the array arr[]
    for i in range(n):
 
        # Calculate remaining sum
        temp = sum - arr[i]
 
        # If sum is divisible by K
        if (temp % K == 0) :
 
            # If res ==-1 or mini is greater
            # than arr[i]
            if (res == -1 or mini > arr[i]) :
 
                # Update res and mini
                res = i + 1
                mini = arr[i]
    return res;
 
# Driver Code
arr = [ 14, 7, 8, 2, 4 ]
K = 7
N = len(arr)
print(findIndex(arr, N, K))
 
# This code is contributed by sanjoy_62.

C#

// C# program to implement 
// the above approach 
using System;
 
class GFG{
     
// Function to find index of the smallest
// array element required to be removed 
// to make sum divisible by K 
static int findIndex(int[] arr, int n, int K) 
{ 
     
    // Stores sum of array elements 
    int sum = 0; 
   
    // Stores index of the smallest
    // element removed from the array
    // to make sum divisible by K 
    int res = -1; 
   
    // Stores the smallest element 
    // removed from the array to 
    // make sum divisible by K 
    int mini = (int)1e9; 
   
    // Traverse the array, arr[] 
    for(int i = 0; i < n; i++)
    { 
         
        // Update sum 
        sum += arr[i]; 
    } 
   
    // Traverse the array arr[] 
    for(int i = 0; i < n; i++) 
    { 
         
        // Calculate remaining sum 
        int temp = sum - arr[i]; 
   
        // If sum is divisible by K 
        if (temp % K == 0)
        { 
             
            // If res ==-1 or mini is greater 
            // than arr[i] 
            if (res == -1 || mini > arr[i])
            { 
                 
                // Update res and mini 
                res = i + 1; 
                mini = arr[i]; 
            } 
        } 
    } 
    return res; 
} 
 
// Driver code    
static void Main() 
{
    int[] arr = { 14, 7, 8, 2, 4 }; 
    int K = 7; 
    int N = arr.Length; 
     
    Console.WriteLine(findIndex(arr, N, K));  
}
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find index of the smallest array element
// required to be removed to make sum divisible by K
function findIndex(arr,n,K)
{
 
    // Stores sum of array elements
    let sum = 0;
 
    // Stores index of the smallest element
    // removed from the array to make sum
    // divisible by K
    let res = -1;
 
    // Stores the smallest element removed
    // from the array to make sum divisible by K
    let mini = parseInt( 1e9);
 
    // Traverse the array, arr[]
    for (let i = 0; i < n; i++)
    {
 
        // Update sum
        sum += arr[i];
    }
 
    // Traverse the array arr[]
    for (let i = 0; i < n; i++)
    {
 
        // Calculate remaining sum
        let temp = sum - arr[i];
 
        // If sum is divisible by K
        if (temp % K == 0)
        {
 
            // If res ==-1 or mini is greater
            // than arr[i]
            if (res == -1 || mini > arr[i])
            {
 
                // Update res and mini
                res = i + 1;
                mini = arr[i];
            }
        }
    }
    return res;
}
 
// Driver Code
 
    let arr = [ 14, 7, 8, 2, 4 ];
    let K = 7;
    let N = arr.length;
    document.write(findIndex(arr, N, K));
 
 
// This code is contributed by sravan kumar
 
</script>

Output:

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

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!