Dados tres enteros N , S y K , la tarea es crear una array de N enteros positivos tal que el OR bit a bit de dos elementos consecutivos cualquiera de la array sea impar y haya exactamente K subarreglos con una suma igual a S donde 1 ≤ K ≤ norte / 2 .
Ejemplos:
Entrada: N = 4, K = 2, S = 6
Salida: 6 7 6 7
Aquí, hay exactamente 2 subarreglo {6} y {6}
cuya suma es 6 y el OR bit a bit de
cualquier elemento adyacente es impar.
Entrada: N = 8, K = 3, S = 12
Salida: 12 13 12 13 12 13 13 13
Acercarse:
- Observe un patrón aquí {S, P, S, P, S, P, …, P, P, P, P} .
- Aquí P es un número impar > S y después de cada S hay una ocurrencia de P . Se sabe que el OR bit a bit con un número impar es siempre un número impar, por lo que se confirma que el OR bit a bit de cada elemento adyacente es un número impar.
- Ahora, coloque exactamente el número K de S en el patrón anterior de la array.
- Excepto S todos los elementos (que son P) son mayores que S, por lo que no puede haber ningún subarreglo cuya suma sea exactamente S que no sean esos K subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to print the
// contents of an array
void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
// Function to generate and print
// the required array
void findArray(int n, int k, int s)
{
// Initially all the positions are empty
int vis[n] = { 0 };
// To store the count of positions
// i such that arr[i] = s
int cnt = 0;
// To store the final array elements
int arr[n];
for (int i = 0; i < n && cnt < k; i += 2) {
// Set arr[i] = s and the gap between
// them is exactly 2 so in for loop
// we use i += 2
arr[i] = s;
// Mark the i'th position as visited
// as we put arr[i] = s
vis[i] = 1;
// Increment the count
cnt++;
}
int val = s;
// Finding the next odd number after s
if (s % 2 == 0)
val++;
else
val = val + 2;
for (int i = 0; i < n; i++) {
if (vis[i] == 0) {
// If the i'th position is not visited
// it means we did not put any value
// at position i so we put 1 now
arr[i] = val;
}
}
// Print the final array
printArr(arr, n);
}
// Driver code
int main()
{
int n = 8, k = 3, s = 12;
findArray(n, k, s);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Utility function to print the
// contents of an array
static void printArr(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
// Function to generate and print
// the required array
static void findArray(int n, int k, int s)
{
// Initially all the positions are empty
int vis[] = new int[n] ;
// To store the count of positions
// i such that arr[i] = s
int cnt = 0;
// To store the final array elements
int arr[] = new int[n];
for (int i = 0; i < n && cnt < k; i += 2)
{
// Set arr[i] = s and the gap between
// them is exactly 2 so in for loop
// we use i += 2
arr[i] = s;
// Mark the i'th position as visited
// as we put arr[i] = s
vis[i] = 1;
// Increment the count
cnt++;
}
int val = s;
// Finding the next odd number after s
if (s % 2 == 0)
val++;
else
val = val + 2;
for (int i = 0; i < n; i++)
{
if (vis[i] == 0)
{
// If the i'th position is not visited
// it means we did not put any value
// at position i so we put 1 now
arr[i] = val;
}
}
// Print the final array
printArr(arr, n);
}
// Driver code
public static void main (String[] args)
{
int n = 8, k = 3, s = 12;
findArray(n, k, s);
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach # Utility function to print the # contents of an array def printArr(arr, n) : for i in range(n) : print(arr[i], end= " "); # Function to generate and print # the required array def findArray(n, k, s) : # Initially all the positions are empty vis = [0] * n; # To store the count of positions # i such that arr[i] = s cnt = 0; # To store the final array elements arr = [0] * n; i = 0; while (i < n and cnt < k) : # Set arr[i] = s and the gap between # them is exactly 2 so in for loop # we use i += 2 arr[i] = s; # Mark the i'th position as visited # as we put arr[i] = s vis[i] = 1; # Increment the count cnt += 1; i += 2; val = s; # Finding the next odd number after s if (s % 2 == 0) : val += 1; else : val = val + 2; for i in range(n) : if (vis[i] == 0) : # If the i'th position is not visited # it means we did not put any value # at position i so we put 1 now arr[i] = val; # Print the final array printArr(arr, n); # Driver code if __name__ == "__main__" : n = 8; k = 3; s = 12; findArray(n, k, s); # This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Utility function to print the
// contents of an array
static void printArr(int []arr, int n)
{
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
// Function to generate and print
// the required array
static void findArray(int n, int k, int s)
{
// Initially all the positions are empty
int []vis = new int[n] ;
// To store the count of positions
// i such that arr[i] = s
int cnt = 0;
// To store the final array elements
int []arr = new int[n];
for (int i = 0; i < n && cnt < k; i += 2)
{
// Set arr[i] = s and the gap between
// them is exactly 2 so in for loop
// we use i += 2
arr[i] = s;
// Mark the i'th position as visited
// as we put arr[i] = s
vis[i] = 1;
// Increment the count
cnt++;
}
int val = s;
// Finding the next odd number after s
if (s % 2 == 0)
val++;
else
val = val + 2;
for (int i = 0; i < n; i++)
{
if (vis[i] == 0)
{
// If the i'th position is not visited
// it means we did not put any value
// at position i so we put 1 now
arr[i] = val;
}
}
// Print the final array
printArr(arr, n);
}
// Driver code
public static void Main()
{
int n = 8, k = 3, s = 12;
findArray(n, k, s);
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// javascript implementation of the approach
// Utility function to print the
// contents of an array
function printArr(arr , n) {
for (i = 0; i < n; i++)
document.write(arr[i] + " ");
}
// Function to generate and print
// the required array
function findArray(n , k , s) {
// Initially all the positions are empty
var vis = Array(n).fill(0);
// To store the count of positions
// i such that arr[i] = s
var cnt = 0;
// To store the final array elements
var arr = Array(n).fill(0);
for (i = 0; i < n && cnt < k; i += 2) {
// Set arr[i] = s and the gap between
// them is exactly 2 so in for loop
// we use i += 2
arr[i] = s;
// Mark the i'th position as visited
// as we put arr[i] = s
vis[i] = 1;
// Increment the count
cnt++;
}
var val = s;
// Finding the next odd number after s
if (s % 2 == 0)
val++;
else
val = val + 2;
for (i = 0; i < n; i++) {
if (vis[i] == 0) {
// If the i'th position is not visited
// it means we did not put any value
// at position i so we put 1 now
arr[i] = val;
}
}
// Print the final array
printArr(arr, n);
}
// Driver code
var n = 8, k = 3, s = 12;
findArray(n, k, s);
// This code contributed by umadevi9616
</script>
Producción:
12 13 12 13 12 13 13 13
Complejidad de tiempo: O(N)