Given an array arr[] consisting of N integers and an integer K, the task is to find the sum of the array elements possible by traversing the array and adding arr[i] / K, K number of times at the end of the array, if arr[i] is divisible by K. Otherwise, stop the traversal.
Examples:
Input: arr[] = {4, 6, 8, 2}, K = 2
Output: 44
Explanation:
The following operations are performed:
- For arr[0](= 4): arr[0](= 4) is divisible by 2, therefore append 4/2 = 2, 2 numbers of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2}.
- For arr[1](= 6): arr[1](= 6) is divisible by 2, therefore append 6/2 = 3, 2 number of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2, 3, 3}.
- For arr[2](= 8): arr[2](= 8) is divisible by 2, therefore append 8/2 = 4, 2 number of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2, 3, 3, 4, 4}.
- For arr[3](= 2): arr[3](= 2) is divisible by 2, therefore append 2/2 = 1, 2 number of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1}.
- For arr[4](= 2): arr[4](= 2) is divisible by 2, therefore append 2/2 = 1, 2 number of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1}.
- For arr[5](= 2): arr[5](= 2) is divisible by 2, therefore append 2/2 = 1, 2 number of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2, 3, 3, 4, 4, 1, 1, 1, 1, 1, 1}.
After completing the above steps, the sum of the array elements is = 4 + 6 + 8 + 2 + 2 + 2 + 3 + 3 + 4 + 4 + 1 + 1 + 1 + 1 + 1 + 1 = 44.
Input: arr[] = {4, 6, 8, 9}, K = 2
Output: 45
Naive Approach: The simplest approach is to solve the given problem is to traverse the given array and add the value (arr[i]/K) K a number of times at the end of the array. After completing the above steps, print the sum of the array elements.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of array// elements after adding arr[i] / K// to the end of the array if arr[i]// is divisible by Kint sum(int arr[], int N, int K){ // Stores the sum of the array int sum = 0; vector<long long> v; // Traverse the array arr[] for (int i = 0; i < N; i++) { v.push_back(arr[i]); } // Traverse the vector for (int i = 0; i < v.size(); i++) { // If v[i] is divisible by K if (v[i] % K == 0) { long long x = v[i] / K; // Iterate over the range // [0, K] for (int j = 0; j < K; j++) { // Update v v.push_back(x); } } // Otherwise else break; } // Traverse the vector v for (int i = 0; i < v.size(); i++) sum = sum + v[i]; // Return the sum of the updated array return sum;}// Driver Codeint main(){ int arr[] = { 4, 6, 8, 2 }; int K = 2; int N = sizeof(arr) / sizeof(arr[0]); cout << sum(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to calculate sum of array// elements after adding arr[i] / K// to the end of the array if arr[i]// is divisible by Kstatic int sum(int arr[], int N, int K){ // Stores the sum of the array int sum = 0; ArrayList<Integer> v = new ArrayList<>(); // Traverse the array arr[] for(int i = 0; i < N; i++) { v.add(arr[i]); } // Traverse the vector for(int i = 0; i < v.size(); i++) { // If v[i] is divisible by K if (v.get(i) % K == 0) { int x = v.get(i) / K; // Iterate over the range // [0, K] for(int j = 0; j < K; j++) { // Update v v.add(x); } } // Otherwise else break; } // Traverse the vector v for(int i = 0; i < v.size(); i++) sum = sum + v.get(i); // Return the sum of the updated array return sum;}// Driver Codepublic static void main(String[] args){ int arr[] = { 4, 6, 8, 2 }; int K = 2; int N = arr.length; System.out.println(sum(arr, N, K));}}// This code is contributed by Kingash |
Python3
# Python3 program for the above approach# Function to calculate sum of array# elements after adding arr[i] / K# to the end of the array if arr[i]# is divisible by Kdef summ(arr, N, K): # Stores the sum of the array sum = 4 v = [i for i in arr] # Traverse the vector for i in range(len(v)): # If v[i] is divisible by K if (v[i] % K == 0): x = v[i] // K # Iterate over the range # [0, K] for j in range(K): # Update v v.append(x) # Otherwise else: break # Traverse the vector v for i in range(len(v)): sum = sum + v[i] # Return the sum of the updated array return sum# Driver Codeif __name__ == '__main__': arr = [ 4, 6, 8, 2 ] K = 2 N = len(arr) print(summ(arr, N, K))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to calculate sum of array // elements after adding arr[i] / K // to the end of the array if arr[i] // is divisible by K static int sum(int[] arr, int N, int K) { // Stores the sum of the array int sum = 0; List<int> v = new List<int>(); // Traverse the array arr[] for (int i = 0; i < N; i++) { v.Add(arr[i]); } // Traverse the vector for (int i = 0; i < v.Count; i++) { // If v[i] is divisible by K if (v[i] % K == 0) { int x = v[i] / K; // Iterate over the range // [0, K] for (int j = 0; j < K; j++) { // Update v v.Add(x); } } // Otherwise else break; } // Traverse the vector v for (int i = 0; i < v.Count; i++) sum = sum + v[i]; // Return the sum of the updated array return sum; } // Driver Code public static void Main(string[] args) { int[] arr = { 4, 6, 8, 2 }; int K = 2; int N = arr.Length; Console.WriteLine(sum(arr, N, K)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to calculate sum of array// elements after adding arr[i] / K// to the end of the array if arr[i]// is divisible by Kfunction sum(arr, N, K){ // Stores the sum of the array var sum = 0; var v = []; // Traverse the array arr[] for (var i = 0; i < N; i++) { v.push(arr[i]); } // Traverse the vector for (var i = 0; i < v.length; i++) { // If v[i] is divisible by K if (v[i] % K == 0) { var x = v[i] / K; // Iterate over the range // [0, K] for (var j = 0; j < K; j++) { // Update v v.push(x); } } // Otherwise else break; } // Traverse the vector v for (var i = 0; i < v.length; i++) sum = sum + v[i]; // Return the sum of the updated array return sum;}// Driver Codevar arr = [4, 6, 8, 2];var K = 2;var N = arr.length;document.write( sum(arr, N, K));</script> |
Output:
44
Time Complexity: O(N * K * log N)
Auxiliary Space: O(M), M is the maximum element of the array.
Efficient Approach: The above approach can also be optimized based on the following observations:
- If arr[i] is divisible by K, then adding arr[i] / K, K times increases the sum by arr[i].
- Therefore, the idea is to only push the arr[i] / K only once at the end of the vector.
Follow the steps below to solve the problem:
- Initialize a variable, say sum as 0 that stores the sum of all the array elements array A[].
- Initialize an array, say A[] and store all the array elements arr[] in A[].
- Initialize a variable, say flag as 0 that stores whether the element is to be added at the end of the array or not.
- Traverse the array A[] and perform the following steps:
- If the value flag is 0 and A[i] is divisible by K, then push A[i] at the end of V.
- Otherwise, update the value of flag as 1.
- Increment the value of the sum by V[i % N].
- After completing the above steps, print the value of the sum as the resultant sum.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate sum of array// elements after adding arr[i] / K// to the end of the array if arr[i]// is divisible by Kint sum(int arr[], int N, int K){ // Stores the sum of the array int sum = 0; // Stores the array elements vector<int> v; // Traverse the array for (int i = 0; i < N; i++) { v.push_back(arr[i]); } // Stores if the operation // should be formed or not bool flag = 0; // Traverse the vector V for (int i = 0; i < v.size(); i++) { // If flag is false and if // v[i] is divisible by K if (!flag && v[i] % K == 0) v.push_back(v[i] / K); // Otherwise, set flag as true else { flag = 1; } // Increment the sum by v[i % N] sum = sum + v[i % N]; } // Return the resultant sum return sum;}// Driver Codeint main(){ int arr[] = { 4, 6, 8, 2 }; int K = 2; int N = sizeof(arr) / sizeof(arr[0]); cout << sum(arr, N, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to calculate sum of array // elements after adding arr[i] / K // to the end of the array if arr[i] // is divisible by K static int sum(int arr[], int N, int K) { // Stores the sum of the array int sum = 0; // Stores the array elements ArrayList<Integer> v = new ArrayList<Integer>(); // Traverse the array for (int i = 0; i < N; i++) { v.add(arr[i]); } // Stores if the operation // should be formed or not boolean flag = false; // Traverse the vector V for (int i = 0; i < v.size(); i++) { // If flag is false and if // v[i] is divisible by K if (!flag && v.get(i) % K == 0) v.add(v.get(i) / K); // Otherwise, set flag as true else { flag = true; } // Increment the sum by v[i % N] sum = sum + v.get(i % N); } // Return the resultant sum return sum; } // Driver Code public static void main (String[] args) { int arr[] = { 4, 6, 8, 2 }; int K = 2; int N = arr.length; System.out.println(sum(arr, N, K)); }}// This code is contributed by Dharanendra L V. |
Python3
# Python program for the above approach# Function to calculate sum of array# elements after adding arr[i] / K# to the end of the array if arr[i]# is divisible by Kdef Sum(arr, N, K): # Stores the sum of the array sum = 0 # Stores the array elements v = [] # Traverse the array for i in range(N): v.append(arr[i]) # Stores if the operation # should be formed or not flag = False i = 0 lenn = len(v) # Traverse the vector V while(i < lenn): # If flag is false and if # v[i] is divisible by K if( flag == False and (v[i] % K == 0)): v.append(v[i]//K) # Otherwise, set flag as true else: flag = True # Increment the sum by v[i % N] sum += v[i % N] i += 1 lenn = len(v) # Return the resultant sum return sum# Driver Codearr = [ 4, 6, 8, 2]K = 2N = len(arr)print(Sum(arr, N, K)) # This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to calculate sum of array// elements after adding arr[i] / K// to the end of the array if arr[i]// is divisible by Kstatic int sum(int []arr, int N, int K){ // Stores the sum of the array int sum = 0; // Stores the array elements List<int> v = new List<int>(); // Traverse the array for(int i = 0; i < N; i++) { v.Add(arr[i]); } // Stores if the operation // should be formed or not bool flag = false; // Traverse the vector V for(int i = 0; i < v.Count; i++) { // If flag is false and if // v[i] is divisible by K if (!flag && v[i] % K == 0) v.Add(v[i] / K); // Otherwise, set flag as true else { flag = true; } // Increment the sum by v[i % N] sum = sum + v[i % N]; } // Return the resultant sum return sum;}// Driver Codestatic void Main(){ int[] arr = { 4, 6, 8, 2 }; int K = 2; int N = arr.Length; Console.WriteLine(sum(arr, N, K));}}// This code is contributed by SoumikMondal |
Javascript
<script>// javascript program for the above approach// Function to calculate sum of array// elements after adding arr[i] / K// to the end of the array if arr[i]// is divisible by Kfunction sum(arr, N, K){ // Stores the sum of the array var sum = 0; var i; // Stores the array elements var v = []; // Traverse the array for (i = 0; i < N; i++) { v.push(arr[i]); } // Stores if the operation // should be formed or not var flag = 0; // Traverse the vector V for (i = 0; i < v.length; i++) { // If flag is false and if // v[i] is divisible by K if (!flag && v[i] % K == 0) v.push(v[i] / K); // Otherwise, set flag as true else { flag = 1; } // Increment the sum by v[i % N] sum = sum + v[i % N]; } // Return the resultant sum return sum;}// Driver Code var arr = [4, 6, 8, 2]; var K = 2; var N = arr.length; document.write(sum(arr, N, K));</script> |
Output:
44
Time Complexity: O(N * log N)
Auxiliary Space: O(N * log 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!
