Dado un arreglo arr[] que consta de N enteros positivos y un entero positivo K , la tarea es actualizar el arreglo dado reemplazando los subarreglos que son menores que K con la suma de los elementos en ese subarreglo .
Ejemplos:
Entrada: arr[] = {200, 6, 36, 612, 121, 66, 63, 39, 668, 108}, K = 100
Salida: 200 42 612 121 168 668 108
Explicación:
El subarreglo arr[1, 2] es decir, {6, 36} tienen elementos menores que K(= 100). Entonces, sumarlos e insertarlos en la array como 6 + 36 = 42.
El subarreglo arr[5, 7] es decir, {66, 63, 39} tiene elementos menores que K(= 100). Entonces, sumarlos e insertarlos en la array como 66 + 63 + 39 = 168.
La array modificada es {200, 42, 612, 121, 168, 668, 108}Entrada: arr[] = {50, 25, 90, 21, 30}, K = 95
Salida: 216
Enfoque: el problema dado se puede resolver recorriendo la array y manteniendo el registro de la suma que tiene todos los elementos menores que K y actualizando la array en consecuencia. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable, diga suma como 0 que almacena la suma del subarreglo.
- Inicialice el vector , digamos res[] que almacena la array actualizada arr[] que cumple con los criterios dados.
- Recorra la array dada y si el valor de arr[i] < K , actualice el valor de sum como sum + arr[i] . De lo contrario, actualice el valor de sum como 0 y agregue el valor sum y arr[i] al vector res[] .
- Después de completar los pasos anteriores, imprima el valor almacenado en el vector res[] .
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 replace all the subarray
// having values < K with their sum
void updateArray(vector<int>& arr, int K)
{
// Stores the sum of subarray having
// elements less than K
int sum = 0;
// Stores the updated array
vector<int> res;
// Traverse the array
for (int i = 0; i < (int)arr.size(); i++) {
// Update the sum
if (arr[i] < K) {
sum += arr[i];
}
// Otherwise, update the vector
else {
if (sum != 0) {
res.push_back(sum);
}
sum = 0;
res.push_back(arr[i]);
}
}
if (sum != 0)
res.push_back(sum);
// Print the result
for (auto& it : res)
cout << it << ' ';
}
// Driver Code
int main()
{
vector<int> arr = { 200, 6, 36, 612, 121,
66, 63, 39, 668, 108 };
int K = 100;
updateArray(arr, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to replace all the subarray
// having values < K with their sum
static void updateArray(int []arr, int K)
{
// Stores the sum of subarray having
// elements less than K
int sum = 0;
// Stores the updated array
ArrayList<Integer> res
= new ArrayList<Integer>();
// Traverse the array
for (int i = 0; i < arr.length; i++) {
// Update the sum
if (arr[i] < K) {
sum += arr[i];
}
// Otherwise, update the vector
else {
if (sum != 0) {
res.add(sum);
}
sum = 0;
res.add(arr[i]);
}
}
if (sum != 0)
res.add(sum);
// Print the result
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
}
// Driver Code
public static void main(String []args)
{
int []arr = {200, 6, 36, 612, 121,
66, 63, 39, 668, 108 };
int K = 100;
updateArray(arr, K);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Python3
# python program for the above approach # Function to replace all the subarray # having values < K with their sum def updateArray(arr, K): # Stores the sum of subarray having # elements less than K sum = 0 # Stores the updated array res = [] # Traverse the array for i in range(0, int(len(arr))): # Update the sum if (arr[i] < K): sum += arr[i] # Otherwise, update the vector else: if (sum != 0): res.append(sum) sum = 0 res.append(arr[i]) if (sum != 0): res.append(sum) # Print the result for it in res: print(it, end=" ") # Driver Code if __name__ == "__main__": arr = [200, 6, 36, 612, 121, 66, 63, 39, 668, 108] K = 100 updateArray(arr, K) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to replace all the subarray
// having values < K with their sum
static void updateArray(List<int> arr, int K)
{
// Stores the sum of subarray having
// elements less than K
int sum = 0;
// Stores the updated array
List<int> res = new List<int>();
// Traverse the array
for (int i = 0; i < arr.Count; i++) {
// Update the sum
if (arr[i] < K) {
sum += arr[i];
}
// Otherwise, update the vector
else {
if (sum != 0) {
res.Add(sum);
}
sum = 0;
res.Add(arr[i]);
}
}
if (sum != 0)
res.Add(sum);
// Print the result
foreach(int it in res) Console.Write(it + " ");
}
// Driver Code
public static void Main()
{
List<int> arr
= new List<int>{ 200, 6, 36, 612, 121,
66, 63, 39, 668, 108 };
int K = 100;
updateArray(arr, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to replace all the subarray
// having values < K with their sum
function updateArray(arr, K) {
// Stores the sum of subarray having
// elements less than K
let sum = 0;
// Stores the updated array
let res = [];
// Traverse the array
for (let i = 0; i < arr.length; i++) {
// Update the sum
if (arr[i] < K) {
sum += arr[i];
}
// Otherwise, update the vector
else {
if (sum != 0) {
res.push(sum);
}
sum = 0;
res.push(arr[i]);
}
}
if (sum != 0)
res.push(sum);
// Print the result
for (let it of res)
document.write(it + ' ');
}
// Driver Code
let arr = [200, 6, 36, 612, 121,
66, 63, 39, 668, 108];
let K = 100;
updateArray(arr, K);
// This code is contributed by Potta Lokesh
</script>
200 42 612 121 168 668 108
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por niteeshn15 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA