Dada una secuencia de enteros de longitud par ‘n’, la tarea es encontrar el número mínimo de operaciones requeridas para convertir la secuencia para seguir la regla a[i]=a[i+2] donde ‘i’ es el índice.
La operación aquí es reemplazar cualquier elemento de la secuencia con cualquier elemento.
Ejemplos:
Input : n=4 ; Array : 3, 1, 3, 2 Output : 1 If we change the last element to '1' then, the sequence will become 3, 1, 3, 1 (satisfying the condition) So, only 1 replacement is required. Input : n=6 ; Array : 105 119 105 119 105 119 Output : 0 As the sequence is already in the required state. So, no replacement of elements is required.
Planteamiento: Como vemos que los índices 0, 2,…, n-2 están conectados de forma independiente y 1, 3, 5,…, n están conectados de forma independiente y deben tener el mismo valor. Asi que,
- Tenemos que encontrar el número que aparece más en ambas secuencias (par e impar) almacenando los números y su frecuencia en un mapa.
- Luego, cualquier otro número en esa secuencia deberá reemplazarse con el número que aparece más en la misma secuencia.
- Finalmente, la cuenta de reemplazos del paso anterior será la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the minimum replacements
int minReplace(int a[], int n)
{
int i;
// Map to store the frequency of
// the numbers at the even indices
map<int, int> te;
// Map to store the frequency of
// the numbers at the odd indices
map<int, int> to;
for (i = 0; i < n; i++)
{
// Checking if the index
// is odd or even
if (i % 2 == 0)
// If the number is already present then,
// just increase the occurrence by 1
te[a[i]]++;
else
// If the number is already present then,
// just increase the occurrence by 1
to[a[i]]++;
}
// To store the character with
// maximum frequency in even indices.
int me = -1;
// To store the character with
// maximum frequency in odd indices.
int mo = -1;
// To store the frequency of the
// maximum occurring number in even indices.
int ce = -1;
// To store the frequency of the
// maximum occurring number in odd indices.
int co = -1;
// Iterating over Map of even indices to
// get the maximum occurring number.
for (auto it : te)
{
if (it.second > ce)
{
ce = it.second;
me = it.first;
}
}
// Iterating over Map of odd indices to
// get the maximum occurring number.
for (auto it : to)
{
if (it.second > co)
{
co = it.second;
mo = it.first;
}
}
// To store the final answer
int res = 0;
for (i = 0; i < n; i++)
{
if (i % 2 == 0)
{
// If the index is even but
// a[i] != me
// then a[i] needs to be replaced
if (a[i] != me) res++;
}
else
{
// If the index is odd but
// a[i] != mo
// then a[i] needs to be replaced
if (a[i] != mo) res++;
}
}
return res;
}
// Driver Code
int main()
{
int n = 4;
int a[] = {3, 1, 3, 2};
cout << minReplace(a, n) << endl;
return 0;
}
// This code is contributed by
// sanjeev2552
Java
// Java implementation of the approach
import java.util.HashMap;
class GFG {
// Function to return the minimum replacements
public static int minReplace(int a[], int n)
{
int i;
// Map to store the frequency of
// the numbers at the even indices
HashMap<Integer, Integer> te = new HashMap<>();
// Map to store the frequency of
// the numbers at the odd indices
HashMap<Integer, Integer> to = new HashMap<>();
for (i = 0; i < n; i++) {
// Checking if the index
// is odd or even
if (i % 2 == 0) {
// If the number is already present then,
// just increase the occurrence by 1
if (te.containsKey(a[i]))
te.put(a[i], te.get(a[i]) + 1);
else
te.put(a[i], 1);
}
else {
// If the number is already present then,
// just increase the occurrence by 1
if (to.containsKey(a[i]))
to.put(a[i], to.get(a[i]) + 1);
else
to.put(a[i], 1);
}
}
// To store the character with
// maximum frequency in even indices.
int me = -1;
// To store the character with
// maximum frequency in odd indices.
int mo = -1;
// To store the frequency of the
// maximum occurring number in even indices.
int ce = -1;
// To store the frequency of the
// maximum occurring number in odd indices.
int co = -1;
// Iterating over Map of even indices to
// get the maximum occurring number.
for (Integer It : te.keySet()) {
if (te.get(It) > ce) {
ce = te.get(It);
me = It;
}
}
// Iterating over Map of odd indices to
// get the maximum occurring number.
for (Integer It : to.keySet()) {
if (to.get(It) > co) {
co = to.get(It);
mo = It;
}
}
// To store the final answer
int res = 0;
for (i = 0; i < n; i++) {
if (i % 2 == 0) {
// If the index is even but
// a[i] != me
// then a[i] needs to be replaced
if (a[i] != me)
res++;
}
else {
// If the index is odd but
// a[i] != mo
// then a[i] needs to be replaced
if (a[i] != mo)
res++;
}
}
return res;
}
// Driver code
public static void main(String[] args)
{
int n;
n = 4;
int a[] = { 3, 1, 3, 2 };
System.out.println(minReplace(a, n));
}
}
Python3
# Python3 implementation of the approach # Function to return the minimum replacements def minReplace(a: list, n) -> int: # Map to store the frequency of # the numbers at the even indices te = dict() # Map to store the frequency of # the numbers at the odd indices to = dict() for i in range(n): # Checking if the index # is odd or even if i % 2 == 0: # If the number is already present then, # just increase the occurrence by 1 if a[i] not in te: te[a[i]] = 1 else: te[a[i]] += 1 else: # If the number is already present then, # just increase the occurrence by 1 if a[i] not in to: to[a[i]] = 1 else: to[a[i]] += 1 # To store the character with # maximum frequency in even indices. me = -1 # To store the character with # maximum frequency in odd indices. mo = -1 # To store the frequency of the # maximum occurring number in even indices. ce = -1 # To store the frequency of the # maximum occurring number in odd indices. co = -1 # Iterating over Map of even indices to # get the maximum occurring number. for it in te: if te[it] > ce: ce = te[it] me = it # Iterating over Map of odd indices to # get the maximum occurring number. for it in to: if to[it] > co: co = to[it] mo = it # To store the final answer res = 0 for i in range(n): if i % 2 == 0: # If the index is even but # a[i] != me # then a[i] needs to be replaced if a[i] != me: res += 1 else: # If the index is odd but # a[i] != mo # then a[i] needs to be replaced if a[i] != mo: res += 1 return res # Driver Code if __name__ == "__main__": n = 4 a = [3, 1, 3, 2] print(minReplace(a, n)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the minimum replacements
public static int minReplace(int []a, int n)
{
int i;
// Map to store the frequency of
// the numbers at the even indices
Dictionary<int,
int> te = new Dictionary<int,
int>();
// Map to store the frequency of
// the numbers at the odd indices
Dictionary<int,
int> to = new Dictionary<int,
int>();
for (i = 0; i < n; i++)
{
// Checking if the index
// is odd or even
if (i % 2 == 0)
{
// If the number is already present then,
// just increase the occurrence by 1
if (te.ContainsKey(a[i]))
te[a[i]] = te[a[i]] + 1;
else
te.Add(a[i], 1);
}
else
{
// If the number is already present then,
// just increase the occurrence by 1
if (to.ContainsKey(a[i]))
to[a[i]] = te[a[i]] + 1;
else
to.Add(a[i], 1);
}
}
// To store the character with
// maximum frequency in even indices.
int me = -1;
// To store the character with
// maximum frequency in odd indices.
int mo = -1;
// To store the frequency of the
// maximum occurring number in even indices.
int ce = -1;
// To store the frequency of the
// maximum occurring number in odd indices.
int co = -1;
// Iterating over Map of even indices to
// get the maximum occurring number.
foreach (int It in te.Keys)
{
if (te[It] > ce)
{
ce = te[It];
me = It;
}
}
// Iterating over Map of odd indices to
// get the maximum occurring number.
foreach (int It in to.Keys)
{
if (to[It] > co)
{
co = to[It];
mo = It;
}
}
// To store the final answer
int res = 0;
for (i = 0; i < n; i++)
{
if (i % 2 == 0)
{
// If the index is even but
// a[i] != me
// then a[i] needs to be replaced
if (a[i] != me)
res++;
}
else
{
// If the index is odd but
// a[i] != mo
// then a[i] needs to be replaced
if (a[i] != mo)
res++;
}
}
return res;
}
// Driver code
public static void Main(String[] args)
{
int n;
n = 4;
int []a = { 3, 1, 3, 2 };
Console.WriteLine(minReplace(a, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Function to return the minimum replacements
function minReplace(a, n)
{
var i;
// Map to store the frequency of
// the numbers at the even indices
var te = new Map();
// Map to store the frequency of
// the numbers at the odd indices
var to = new Map();
for (i = 0; i < n; i++)
{
// Checking if the index
// is odd or even
if (i % 2 == 0)
// If the number is already present then,
// just increase the occurrence by 1
if(te.has(a[i]))
te.set(a[i], te.get(a[i])+1)
else
te.set(a[i],1)
else
// If the number is already present then,
// just increase the occurrence by 1
if(to.has(a[i]))
to.set(a[i], to.get(a[i])+1)
else
to.set(a[i],1)
}
// To store the character with
// maximum frequency in even indices.
var me = -1;
// To store the character with
// maximum frequency in odd indices.
var mo = -1;
// To store the frequency of the
// maximum occurring number in even indices.
var ce = -1;
// To store the frequency of the
// maximum occurring number in odd indices.
var co = -1;
// Iterating over Map of even indices to
// get the maximum occurring number.
te.forEach((value, key) => {
if (value > ce)
{
ce = value;
me = key;
}
});
// Iterating over Map of odd indices to
// get the maximum occurring number.
to.forEach((value, key) => {
if (value > co)
{
co = value;
mo = key;
}
});
// To store the final answer
var res = 0;
for (i = 0; i < n; i++)
{
if (i % 2 == 0)
{
// If the index is even but
// a[i] != me
// then a[i] needs to be replaced
if (a[i] != me)
res++;
}
else
{
// If the index is odd but
// a[i] != mo
// then a[i] needs to be replaced
if (a[i] != mo)
res++;
}
}
return res;
}
// Driver Code
var n = 4;
var a = [3, 1, 3, 2];
document.write( minReplace(a, n) );
</script>
Producción:
1