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:
- Si K es negativo, invierta la array dada y multiplique K con -1 .
- Calcule y almacene la suma del prefijo de la array dada en pre[] .
- Cree la array ans[] para almacenar la respuesta de cada elemento.
- Para cada índice i , si i + K es menor que N , actualice ans[i] = pre[i + k] – pre[i]
- 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.
- 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 .
- 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[] .
- 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