Reemplace cada elemento en una array circular por la suma de los siguientes K elementos

Dada una array circular arr[] de N enteros y un entero K , la tarea es imprimir la array después de las siguientes operaciones:

  • Si K no es negativo, entonces reemplace A[i] con la suma de los siguientes K elementos.
  • Si K es negativo, reemplácelo con la suma de los K elementos anteriores.

Una array cíclica significa que el siguiente elemento del último elemento de la array es el primer elemento y el elemento anterior del primer elemento es el último elemento.

Ejemplos:

Entrada : arr[] = {4, 2, -5, 11}, K = 3
Salida: 8 10 17 1
Explicación: 
Paso 1: Para el índice 0, reemplace arr[0] = arr[1] + arr[2] + arr[3] = 2 + (-5) + 11 = 8 
Paso 2: Para el índice 1, reemplace arr[1] = arr[2] + arr[3] + arr[0] = (-5) + 11 + 4 = 10 
Paso 3: Para el índice 2, reemplace arr[2] = arr[3] + arr[0] + arr[1] = 11 + 4 + 2 = 17 
Paso 4: Para el índice 3, reemplace arr[3 ] = arr[0] + arr[1] + arr[2] = 4 + 2 + -5 = 1 
Por lo tanto, la array resultante es {8, 10, 17, 1}

Entrada: arr[] = {2, 5, 7, 9}, K = -2
Salida: 16 11 7 12
Explicación: 
Paso 1: Para el índice 0, reemplace arr[0] = arr[3] + arr[2] = 9 + 7 = 16 
Paso 2: Para el índice 1, reemplace arr[1] = arr[0] + arr[3] = 2 + 9 = 11 
Paso 3: Para el índice 2, reemplace arr[2] = arr[1 ] + arr[0] = 5 + 2 = 7 
Paso 4: Para el índice 3, reemplace arr[3] = arr[2] + arr[1] = 7 + 5 = 12 
Por lo tanto, la array resultante es {16, 11 , 7, 12}

Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array y recorrer los K elementos siguientes o anteriores , en función del valor de K , para cada elemento de la array e imprimir su suma. Siga los pasos a continuación para resolver el problema:

  • Si el valor de K es negativo, invierta la array y encuentre la suma de los siguientes K elementos.
  • Si el valor de K no es negativo, simplemente encuentre la suma de los siguientes K elementos para cada elemento.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
 
// Function to find the sum of next
// or previous k array elements
vector<int> sumOfKelementsUtil(
    vector<int>& a, int x)
{
    // Size of the array
    int n = a.size();
 
    int count, k, temp;
 
    // Stores the result
    vector<int> ans;
 
    // Iterate the given array
    for (int i = 0; i < n; i++) {
 
        count = 0;
        k = i + 1;
        temp = 0;
 
        // Traverse the k elements
        while (count < x) {
 
            temp += a[k % n];
            count++;
            k++;
        }
 
        // Push the K elements sum
        ans.pb(temp);
    }
 
    // Return the resultant vector
    return ans;
}
 
// Function that prints the sum of next
// K element for each index in the array
void sumOfKelements(vector<int>& arr,
                    int K)
{
    // Size of the array
    int N = (int)arr.size();
 
    // Stores the result
    vector<int> ans;
 
    // If key is negative,
    // reverse the array
    if (K < 0) {
        K = K * (-1);
 
        // Reverse the array
        reverse(arr.begin(),
                arr.end());
 
        // Find the resultant vector
        ans = sumOfKelementsUtil(arr, K);
 
        // Reverse the array again to
        // get the original sequence
        reverse(ans.begin(), ans.end());
    }
 
    // If K is positive
    else {
        ans = sumOfKelementsUtil(arr, K);
    }
 
    // Print the answer
    for (int i = 0; i < N; i++) {
        cout << ans[i] << " ";
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    vector<int> arr = { 4, 2, -5, 11 };
    int K = 3;
 
    // Function Call
    sumOfKelements(arr, K);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
     
//reverse array
static Vector<Integer> reverse(Vector<Integer> a)
{
  int i, n = a.size(), t;
  for (i = 0; i < n / 2; i++)
  {
    t = a.elementAt(i);
    a.set(i, a.elementAt(n - i - 1));
    a.set(n - i - 1, t);
  }
  return a;
}
 
// Function to find the sum of next
// or previous k array elements
static Vector<Integer> sumOfKelementsUtil(
       Vector<Integer>a, int x)
{
  // Size of the array
  int n = a.size();
 
  int count, k, temp;
 
  // Stores the result
  Vector<Integer> ans = new Vector<>();
 
  // Iterate the given array
  for (int i = 0; i < n; i++)
  {
    count = 0;
    k = i + 1;
    temp = 0;
 
    // Traverse the k elements
    while (count < x)
    {
      temp += a.elementAt(k % n);
      count++;
      k++;
    }
 
    // Push the K elements sum
    ans.add(temp);
  }
 
  // Return the resultant vector
  return ans;
}
 
// Function that prints the sum of next
// K element for each index in the array
static void sumOfKelements(Vector<Integer> arr,
                           int K)
{
  // Size of the array
  int N = (int)arr.size();
 
  // Stores the result
  Vector<Integer> ans = new Vector<>();
 
  // If key is negative,
  // reverse the array
  if (K < 0)
  {
    K = K * (-1);
 
    // Reverse the array
    arr =  reverse(arr);
 
    // Find the resultant vector
    ans = sumOfKelementsUtil(arr, K);
 
    // Reverse the array again to
    // get the original sequence
    ans = reverse(ans);
  }
 
  // If K is positive
  else
  {
    ans = sumOfKelementsUtil(arr, K);
  }
 
  // Print the answer
  for (int i = 0; i < N; i++)
  {
    System.out.print(ans.elementAt(i) + " ");
  }
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array arr[]
    Vector<Integer> arr = new Vector<>();
    arr.add(4);
    arr.add(2);
    arr.add(-5);
    arr.add(11);
    int K = 3;
 
    // Function Call
    sumOfKelements(arr, K);
 
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for
# the above approach
 
# Function to find the sum of next
# or previous k array elements
def sumOfKelementsUtil(a, x):
 
    # Size of the array
    n = len(a)
     
    # Stores the result
    ans = []
 
    # Iterate the given array
    for i in range(n):
        count = 0
        k = i + 1
        temp = 0
 
        # Traverse the k elements
        while (count < x):
            temp += a[k % n]
            count += 1
            k += 1
 
        # Push the K elements sum
        ans.append(temp)
    
    # Return the resultant vector
    return ans
 
# Function that prints the
# sum of next K element for
# each index in the array
def sumOfKelements(arr, K):
 
    # Size of the array
    N = len(arr)
 
    #Stores the result
    ans = []
 
    # If key is negative,
    # reverse the array
    if (K < 0):
        K = K * (-1)
 
        # Reverse the array
        arr.reverse()
         
        # Find the resultant vector
        ans = sumOfKelementsUtil(arr, K)
 
        #Reverse the array again to
        # get the original sequence
        ans.reverse()
 
    # If K is positive
    else:
        ans = sumOfKelementsUtil(arr, K)
   
    # Print the answer
    for i in range(N):
        print (ans[i], end = " ")
    
# Driver Code
if __name__ == "__main__":
   
    # Given array arr[]
    arr = [4, 2, -5, 11]
    K = 3
 
    # Function Call
    sumOfKelements(arr, K)
 
# This code is contributed by Chitranayal

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
     
// Reverse array
static List<int> reverse(List<int> a)
{
  int i, n = a.Count, t;
  for (i = 0; i < n / 2; i++)
  {
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
  }
  return a;
}
 
// Function to find the sum of next
// or previous k array elements
static List<int> sumOfKelementsUtil(
       List<int>a, int x)
{
  // Size of the array
  int n = a.Count;
 
  int count, k, temp;
 
  // Stores the result
  List<int> ans = new List<int>();
 
  // Iterate the given array
  for (int i = 0; i < n; i++)
  {
    count = 0;
    k = i + 1;
    temp = 0;
 
    // Traverse the k elements
    while (count < x)
    {
      temp += a[k % n];
      count++;
      k++;
    }
 
    // Push the K elements sum
    ans.Add(temp);
  }
 
  // Return the resultant vector
  return ans;
}
 
// Function that prints the sum of next
// K element for each index in the array
static void sumOfKelements(List<int> arr,
                           int K)
{
  // Size of the array
  int N = (int)arr.Count;
 
  // Stores the result
  List<int> ans = new List<int>();
 
  // If key is negative,
  // reverse the array
  if (K < 0)
  {
    K = K * (-1);
 
    // Reverse the array
    arr =  reverse(arr);
 
    // Find the resultant vector
    ans = sumOfKelementsUtil(arr, K);
 
    // Reverse the array again to
    // get the original sequence
    ans = reverse(ans);
  }
 
  // If K is positive
  else
  {
    ans = sumOfKelementsUtil(arr, K);
  }
 
  // Print the answer
  for (int i = 0; i < N; i++)
  {
    Console.Write(ans[i] + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  List<int> arr = new List<int>();
  arr.Add(4);
  arr.Add(2);
  arr.Add(-5);
  arr.Add(11);
  int K = 3;
 
  // Function Call
  sumOfKelements(arr, K);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach
 
   // Function to print the
    // required resultant array
    function sumOfKElements(
        arr, n, k)
    {
  
        // Reverse the array
        let rev = false;
  
        if (k < 0) {
  
            rev = true;
            k *= -1;
            let l = 0, r = n - 1;
  
            // Traverse the range
            while (l < r) {
  
                let tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
                l++;
                r--;
            }
        }
  
        // Store prefix sum
        let dp = Array.from({length: n}, (_, i) => 0);
        dp[0] = arr[0];
  
        // Find the prefix sum
        for (let i = 1; i < n; i++) {
  
            dp[i] += dp[i - 1] + arr[i];
        }
  
        // Store the answer
        let ans = Array.from({length: n}, (_, i) => 0);
  
        // Calculate the answers
        for (let i = 0; i < n; i++) {
  
            if (i + k < n)
                ans[i] = dp[i + k] - dp[i];
            else {
  
                // Count of remaining elements
                let x = k - (n - 1 - i);
  
                // Add the sum of all elements
                // y times
                let y = Math.floor(x / n);
  
                // Add the remaining elements
                let rem = x % n;
  
                // Update ans[i]
                ans[i] = dp[n - 1]
                         - dp[i]
                         + y * dp[n - 1]
                         + (rem - 1 >= 0 ? dp[rem - 1] : 0);
            }
        }
  
        // If array is reversed print
        // ans[] in reverse
        if (rev) {
            for (let i = n - 1; i >= 0; i--) {
                document.write(ans[i] + " ");
            }
        }
        else {
            for (let i = 0; i < n; i++) {
                document.write(ans[i] + " ");
            }
        }
    }
 
// Driver Code
 
   // Given array arr[]
        let arr = [ 4, 2, -5, 11 ];
  
        let N = arr.length;
  
        // Given K
        let K = 3;
  
        // Function
        sumOfKElements(arr, N, K);
 
// This code is contributed by souravghosh0416.
</script>
Producción

8 10 17 1 

Complejidad de tiempo: O(N*K), donde N es la longitud de la array dada y K es el número entero dado.
Espacio Auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar el prefijo sum . Siga los pasos a continuación para resolver el problema:

  1. Si K es negativo, invierta la array dada y multiplique K con -1 .
  2. Calcule y almacene la suma del prefijo de la array dada en pre[] .
  3. Cree la array ans[] para almacenar la respuesta de cada elemento.
  4. Para cada índice i , si i + K es menor que N , actualice ans[i] = pre[i + k] – pre[i]
  5. De lo contrario, agregue la suma de todos los elementos del índice i a N – 1 , encuentre los K – (N – 1 – i) elementos restantes porque los elementos (N – 1 – i) ya se agregaron en el paso anterior.
  6. Sume la suma de todos los elementos floor((K – N – 1 – i)/N) veces y la suma de los elementos restantes de la array dada de 0 a ((K – (N – 1 – i)) % N) – 1 .
  7. Después de calcular la respuesta para cada elemento de la array, verifique si la array se invirtió anteriormente. En caso afirmativo, invierta la array ans[] .
  8. Imprima todos los elementos almacenados en la array ans[] después de los pasos anteriores.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
 
// Function to print the
// required resultant array
void sumOfKElements(int arr[], int n,
                    int k)
{
     
    // Reverse the array
    bool rev = false;
 
    if (k < 0)
    {
        rev = true;
        k *= -1;
        int l = 0, r = n - 1;
 
        // Traverse the range
        while (l < r)
        {
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++;
            r--;
        }
    }
 
    // Store prefix sum
    int dp[n] = {0};
    dp[0] = arr[0];
 
    // Find the prefix sum
    for(int i = 1; i < n; i++)
    {
        dp[i] += dp[i - 1] + arr[i];
    }
 
    // Store the answer
    int ans[n] = {0};
 
    // Calculate the answers
    for(int i = 0; i < n; i++)
    {
        if (i + k < n)
            ans[i] = dp[i + k] - dp[i];
        else
        {
             
            // Count of remaining elements
            int x = k - (n - 1 - i);
 
            // Add the sum of all elements
            // y times
            int y = x / n;
 
            // Add the remaining elements
            int rem = x % n;
 
            // Update ans[i]
            ans[i] = dp[n - 1] - dp[i] +
                 y * dp[n - 1] + (rem - 1 >= 0 ?
                   dp[rem - 1] : 0);
        }
    }
 
    // If array is reversed print
    // ans[] in reverse
    if (rev)
    {
        for(int i = n - 1; i >= 0; i--)
        {
            cout << ans[i] << " ";
        }
    }
    else
    {
        for(int i = 0; i < n; i++)
        {
            cout << ans[i] << " ";
        }
    }
}
 
// Driver Code
int main()
{
     
    // Given array arr[]
    int arr[] = { 4, 2, -5, 11 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Given K
    int K = 3;
 
    // Function
    sumOfKElements(arr, N, K);
}
 
// This code is contributed by SURENDRA_GANGWAR

Java

// Java program for the above approach
import java.io.*;
 
class GFG {
 
    // Function to print the
    // required resultant array
    static void sumOfKElements(
        int arr[], int n, int k)
    {
 
        // Reverse the array
        boolean rev = false;
 
        if (k < 0) {
 
            rev = true;
            k *= -1;
            int l = 0, r = n - 1;
 
            // Traverse the range
            while (l < r) {
 
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
                l++;
                r--;
            }
        }
 
        // Store prefix sum
        int dp[] = new int[n];
        dp[0] = arr[0];
 
        // Find the prefix sum
        for (int i = 1; i < n; i++) {
 
            dp[i] += dp[i - 1] + arr[i];
        }
 
        // Store the answer
        int ans[] = new int[n];
 
        // Calculate the answers
        for (int i = 0; i < n; i++) {
 
            if (i + k < n)
                ans[i] = dp[i + k] - dp[i];
            else {
 
                // Count of remaining elements
                int x = k - (n - 1 - i);
 
                // Add the sum of all elements
                // y times
                int y = x / n;
 
                // Add the remaining elements
                int rem = x % n;
 
                // Update ans[i]
                ans[i] = dp[n - 1]
                         - dp[i]
                         + y * dp[n - 1]
                         + (rem - 1 >= 0 ? dp[rem - 1] : 0);
            }
        }
 
        // If array is reversed print
        // ans[] in reverse
        if (rev) {
            for (int i = n - 1; i >= 0; i--) {
                System.out.print(ans[i] + " ");
            }
        }
        else {
            for (int i = 0; i < n; i++) {
                System.out.print(ans[i] + " ");
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given array arr[]
        int arr[] = { 4, 2, -5, 11 };
 
        int N = arr.length;
 
        // Given K
        int K = 3;
 
        // Function
        sumOfKElements(arr, N, K);
    }
}

Python3

# Python3 program for
# the above approach
 
# Function to print
# required resultant array
def sumOfKElements(arr, n, k):
   
    # Reverse the array
    rev = False;
 
    if (k < 0):
 
        rev = True;
        k *= -1;
        l = 0;
        r = n - 1;
 
        # Traverse the range
        while (l < r):
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l += 1;
            r -= 1;
 
    # Store prefix sum
    dp = [0] * n;
    dp[0] = arr[0];
 
    # Find the prefix sum
    for i in range(1, n):
        dp[i] += dp[i - 1] + arr[i];
 
    # Store the answer
    ans = [0] * n;
 
    # Calculate the answers
    for i in range(n):
        if (i + k < n):
            ans[i] = dp[i + k] - dp[i];
        else:
 
            # Count of remaining
            # elements
            x = k - (n - 1 - i);
 
            # Add the sum of
            # all elements y times
            y = x // n;
 
            # Add the remaining
            # elements
            rem = x % n;
 
            # Update ans[i]
            ans[i] = (dp[n - 1] - dp[i] +
                      y * dp[n - 1] +
                      (dp[rem - 1]
                      if rem - 1 >= 0
                      else 0));
 
    # If array is reversed
    # print ans in reverse
    if (rev):
        for i in range(n - 1, -1, -1):
            print(ans[i], end = " ");
 
    else:
        for i in range(n):
            print(ans[i], end = " ");
 
# Driver Code
if __name__ == '__main__':
   
    # Given array arr
    arr = [4, 2, -5, 11];
 
    N = len(arr);
 
    # Given K
    K = 3;
 
    # Function
    sumOfKElements(arr, N, K);
 
# This code is contributed by 29AjayKumar

C#

// C# program for
// the above approach
using System;
class GFG {
 
// Function to print the
// required resultant array
static void sumOfKElements(int []arr,
                           int n, int k)
{
  // Reverse the array
  bool rev = false;
 
  if (k < 0)
  {
    rev = true;
    k *= -1;
    int l = 0, r = n - 1;
 
    // Traverse the range
    while (l < r)
    {
      int tmp = arr[l];
      arr[l] = arr[r];
      arr[r] = tmp;
      l++;
      r--;
    }
  }
 
  // Store prefix sum
  int []dp = new int[n];
  dp[0] = arr[0];
 
  // Find the prefix sum
  for (int i = 1; i < n; i++)
  {
    dp[i] += dp[i - 1] + arr[i];
  }
 
  // Store the answer
  int []ans = new int[n];
 
  // Calculate the answers
  for (int i = 0; i < n; i++)
  {
    if (i + k < n)
      ans[i] = dp[i + k] - dp[i];
    else
    {
      // Count of remaining elements
      int x = k - (n - 1 - i);
 
      // Add the sum of all elements
      // y times
      int y = x / n;
 
      // Add the remaining elements
      int rem = x % n;
 
      // Update ans[i]
      ans[i] = dp[n - 1] - dp[i] +
               y * dp[n - 1] +
               (rem - 1 >= 0 ?
                dp[rem - 1] : 0);
    }
  }
 
  // If array is reversed print
  // ans[] in reverse
  if (rev)
  {
    for (int i = n - 1; i >= 0; i--)
    {
      Console.Write(ans[i] + " ");
    }
  }
  else
  {
    for (int i = 0; i < n; i++)
    {
      Console.Write(ans[i] + " ");
    }
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int []arr = {4, 2, -5, 11};
 
  int N = arr.Length;
 
  // Given K
  int K = 3;
 
  // Function
  sumOfKElements(arr, N, K);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to print the
// required resultant array
function sumOfKElements(arr, n,
                    k)
{
     
    // Reverse the array
    let rev = false;
 
    if (k < 0)
    {
        rev = true;
        k *= -1;
        let l = 0, r = n - 1;
 
        // Traverse the range
        while (l < r)
        {
            let tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            l++;
            r--;
        }
    }
 
    // Store prefix sum
    let dp = new Uint8Array(n);
    dp[0] = arr[0];
 
    // Find the prefix sum
    for(let i = 1; i < n; i++)
    {
        dp[i] += dp[i - 1] + arr[i];
    }
 
    // Store the answer
    let ans = new Uint8Array(n);
 
    // Calculate the answers
    for(let i = 0; i < n; i++)
    {
        if (i + k < n)
            ans[i] = dp[i + k] - dp[i];
        else
        {
             
            // Count of remaining elements
            let x = k - (n - 1 - i);
 
            // Add the sum of all elements
            // y times
            let y = Math.floor(x / n);
 
            // Add the remaining elements
            let rem = x % n;
 
            // Update ans[i]
            ans[i] = dp[n - 1] - dp[i] +
                y * dp[n - 1] + (rem - 1 >= 0 ?
                dp[rem - 1] : 0);
        }
    }
 
    // If array is reversed print
    // ans[] in reverse
    if (rev)
    {
        for(let i = n - 1; i >= 0; i--)
        {
            document.write(ans[i] + " ");
        }
    }
    else
    {
        for(let i = 0; i < n; i++)
        {
            document.write(ans[i] + " ");
        }
    }
}
 
// Driver Code
 
    // Given array arr[]
    let arr = [ 4, 2, -5, 11 ];
 
    let N = arr.length;
 
    // Given K
    let K = 3;
 
    // Function
    sumOfKElements(arr, N, K);
 
//This code is contributed by Mayank Tyagi
 
</script>
Producción

8 10 17 1 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *