Saturday, 16 Oct 2021

# Sum of array elements possible by appending arr[i] / K to the end of the array K times for array elements divisible by K

Sum of array elements possible by appending arr[i] / K to the end of the array K times for array elements divisible by KGiven 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 = 2Output: 44Explanation:Following operations are performed:For arr(= 4): arr(= 4) is divisible by 2, therefore append 4/2 = 2, 2 number of times at the end of the array. Now, the array modifies to {4, 6, 8, 2, 2, 2}.For arr(= 6): arr(= 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(= 8): arr(= 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(= 2): arr(= 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(= 2): arr(= 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(= 2): arr(= 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 element 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 = 2Output: 45Naive Approach: The simplest approach is to solve the given problem is to traverse the given array and add the value (arr[i]/K) K 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++#include using namespace std;int sum(int arr[], int N, int K){        int sum = 0;    vector v;        for (int i = 0; i < N; i++) {        v.push_back(arr[i]);    }        for (int i = 0;         i < v.size(); i++) {                if (v[i] % K == 0) {            long long x = v[i] / K;                                    for (int j = 0; j < K; j++) {                                v.push_back(x);            }        }                else            break;    }        for (int i = 0; i < v.size(); i++)        sum = sum + v[i];        return sum;}int main(){    int arr[] = { 4, 6, 8, 2 };    int K = 2;    int N = sizeof(arr) / sizeof(arr);    cout