Given an array arr[] and a number K, the task is to make all elements of array divisible by K. To make elements divisible by K, one can perform following operation:
- Choose any index C in the array.
- You are allowed to subtract any value from any of the numbers up to the index C and you are allowed to add any value to any of the elements present after index C.
- The only condition required for the above operation is total sum of values subtracted up to index C can be added to the elements after index C.
Print the value of index C and the difference of subtracted numbers to the numbers added after index C.
Examples:
Input: arr[] = {1, 14, 4, 41, 1}, K = 7
Output: C = 3, difference = 5
Explanation:
Please Refer below for explanation.
Input: arr[] = {1, 10, 19}, K=9
Output: C = 2, difference = 2
Explanation:
Approach:
- Create two auxiliary arrays arr1[] and arr2[].
- The first array arr1[] stores the value of element that can be subtracted from every element to make it divisible by K in arr[].
- The second array arr2[] stores the value of element that can be added to make the element divisible by K.
- Then Iterate over the possible values for the C and find the index in which the sum of subtracted values from arr1[] up to that index is greater than or equal to the sum of the added values to the index after C in arr2[].
Below is the implementation of the above approach:
C++
// C++ implementation to make// the array elements divisible by K#include <bits/stdc++.h>using namespace std;// Function to make array divisiblepair<int,int> makeDivisble(int arr[], int n, int k){ vector<int>b1; vector<int>b2; int c, suml, sumr, index, rem; // For each element of array // how much number to be subtracted // to make it divisible by k for (int i = 0; i < n; i++) b1.push_back(arr[i] % k); // For each element of array // how much number to be added // to make it divisible by K for (int j = 0; j < n; j++) if ((arr[j] % k) != 0) b2.push_back(k - (arr[j] % k)); else b2.push_back(0); c = 0; float mini = INT_MAX; suml = 0; sumr = 0; index = -1; // Calculate minimum difference for (int c = 0; c < n; c++) { suml = accumulate(b1.begin(),b1.begin() + c + 1, 0); sumr = accumulate(b2.begin() + c + 1 , b2.end(), 0); if (suml >= sumr) { rem = suml - sumr; if (rem < mini) { mini = rem; index = c; } } } return make_pair(index, mini);}// Driver Codeint main() { int arr[] = {1, 14, 4, 41, 1}; int k = 7; int n=sizeof(arr)/sizeof(arr[0]); pair<int ,int>ans; ans = makeDivisble(arr, n, k); cout << ans.first << " " << ans.second; return 0;}// This code is contributed by Atul_kumar_Shrivastava |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG { static class Pair{ int first; int second; Pair(int f,int s){ first = f; second = s; } } // Function to make array divisible static Pair makeDivisble(int arr[], int n, int k) { ArrayList<Integer> b1 = new ArrayList<>(); ArrayList<Integer> b2 = new ArrayList<>(); int c, suml, sumr, index, rem; // For each element of array // how much number to be subtracted // to make it divisible by k for (int i = 0; i < n; i++) b1.add(arr[i] % k); // For each element of array // how much number to be added // to make it divisible by K for (int j = 0; j < n; j++) if ((arr[j] % k) != 0) b2.add(k - (arr[j] % k)); else b2.add(0); c = 0; double mini = Integer.MAX_VALUE; suml = 0; sumr = 0; index = -1; // Calculate minimum difference for (c = 0; c < n; c++) { suml = accumulate(b1,0,c + 1); sumr = accumulate(b2,c + 1 ,b2.size()); if (suml >= sumr) { rem = suml - sumr; if (rem < mini) { mini = rem; index = c; } } } return new Pair(index, (int)mini); } static int accumulate(ArrayList<Integer> ll,int i,int j){ int sum = 0; while(i<j){ sum += ll.get(i); i++; } return sum; } public static void main (String[] args) { int arr[] = {1, 14, 4, 41, 1}; int k = 7; int n= arr.length; Pair ans = makeDivisble(arr, n, k); System.out.println(ans.first + " " + ans.second); }}// This code is contributed by aadityaburujwale. |
Python3
# Python implementation to make# the array elements divisible by K# Function to make array divisibledef makeDivisble(arr, k): n = len(arr) b1 =[] b2 =[] # For each element of array # how much number to be subtracted # to make it divisible by k for i in range (n): b1.append(arr[i]% k) # For each element of array # how much number to be added # to make it divisible by K for j in range(n): if ((arr[j]% k)!= 0): b2.append(k-(arr[j]% k)) else: b2.append(0) c = 0 mini = float('inf') suml = 0 sumr = 0 index = -1 # Calculate minimum difference for c in range(0, n+1, 1): suml = sum(b1[ : c + 1]) sumr = sum(b2) if suml>= sumr: rem = suml-sumr if rem<mini: mini = rem index = c return index, mini# Driver Codeif __name__ == "__main__": arr = [1, 14, 4, 41, 1] k = 7 index, diff = makeDivisble(arr, k) print(index, diff) |
C#
using System;using System.Collections.Generic;public class GFG { public static int accumulate(List<int> ll, int i, int j) { int sum = 0; while (i < j) { sum += ll[i]; i++; } return sum; } // Function to make array divisible public static List<int> makeDivisble(int[] arr, int n, int k) { List<int> b1 = new List<int>(); List<int> b2 = new List<int>(); int c, suml, sumr, index, rem; // For each element of array // how much number to be subtracted // to make it divisible by k for (int i = 0; i < n; i++) b1.Add(arr[i] % k); // For each element of array // how much number to be added // to make it divisible by K for (int j = 0; j < n; j++) if ((arr[j] % k) != 0) b2.Add(k - (arr[j] % k)); else b2.Add(0); c = 0; int mini = Int32.MaxValue; suml = 0; sumr = 0; index = -1; // Calculate minimum difference for (c = 0; c < n; c++) { suml = accumulate(b1, 0, c + 1); sumr = accumulate(b2, c + 1, b2.Count); if (suml >= sumr) { rem = suml - sumr; if (rem < mini) { mini = rem; index = c; } } } List<int> ans = new List<int>(); ans.Add(index); ans.Add(mini); return ans; } static public void Main() { int[] arr = { 1, 14, 4, 41, 1 }; int k = 7; int n = arr.Length; List<int> ans = new List<int>(); ans = makeDivisble(arr, n, k); Console.WriteLine(ans[0] + " " + ans[1]); }}// This code is contributed by akashish__ |
Javascript
// JS implementation to make// the array elements divisible by Kfunction accumulate(ll, i, j){ let sum = 0; while(i<j){ sum += ll[i]; i++; } return sum; }// Function to make array divisiblefunction makeDivisble(arr, n, k){ // vector<int>b1; // vector<int>b2; let b1 = [], b2 = []; let c, suml, sumr, index, rem; // For each element of array // how much number to be subtracted // to make it divisible by k for (let i = 0; i < n; i++) b1.push(arr[i] % k); // For each element of array // how much number to be added // to make it divisible by K for (let j = 0; j < n; j++) if ((arr[j] % k) != 0) b2.push(k - (arr[j] % k)); else b2.push(0); c = 0; let mini = Number.MAX_VALUE; suml = 0; sumr = 0; index = -1; // Calculate minimum difference for (let c = 0; c < n; c++) { suml = accumulate(b1,0,c + 1); sumr = accumulate(b2,c + 1 ,b2.length); if (suml >= sumr) { rem = suml - sumr; if (rem < mini) { mini = rem; index = c; } } } return {"first":index, "second":mini};}// Driver Codelet arr = [1, 14, 4, 41, 1];let k = 7;let n=arr.length;let ans = [];ans = makeDivisble(arr, n, k);console.log(ans.first,ans.second);// This code is contributed by akashish__ |
Output:
3 5
Time Complexity: O(N^2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
