Dados dos números enteros N y K , donde N representa un patrón de diamantes con ( 2 * N) -1 filas, la tarea es encontrar el índice de la primera fila hasta la cual hay al menos K estrellas en un patrón de diamantes .
Tenga en cuenta que el valor de K siempre tendrá una respuesta definitiva.
Ejemplos :
Entrada : N = 3, K = 8
Salida : 4
Explicación : Las primeras 4 filas contienen un total de 8 estrellas.
** *
* * *
* *
*
Entrada : N = 5, K = 5
Salida : 3
Enfoque ingenuo: el problema dado se puede resolver simplemente iterando sobre cada fila y manteniendo el recuento del número de estrellas en cada fila. Imprime los dos primeros donde el conteo de estrellas exceda K.
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 find the index of
// required row
void get(int N, int K)
{
// Stores the count of stars
// till ith row
int sum = 0, ans;
// Iterating over the rows
for (int i = 1; i <= 2 * N - 1; i++) {
// Upper half
if (i <= N) {
sum += i;
}
// Lower half
else {
sum += 2 * N - i;
}
// Atleast K stars are found
if (sum >= K) {
ans = i;
break;
}
}
// Print Answer
cout << ans << endl;
}
// Driver Code
int main()
{
int N = 3, K = 8;
get(N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the index of
// required row
static void get(int N, int K)
{
// Stores the count of stars
// till ith row
int sum = 0, ans = 0;
// Iterating over the rows
for (int i = 1; i <= 2 * N - 1; i++) {
// Upper half
if (i <= N) {
sum += i;
}
// Lower half
else {
sum += 2 * N - i;
}
// Atleast K stars are found
if (sum >= K) {
ans = i;
break;
}
}
// Print Answer
System.out.print(ans +"\n");
}
// Driver Code
public static void main(String[] args)
{
int N = 3, K = 8;
get(N, K);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Function to find the index of # required row def get(N, K): # Stores the count of stars # till ith row sum = 0; ans = 0; # Iterating over the rows for i in range(1,2*N): # Upper half if (i <= N): sum += i; # Lower half else: sum += 2 * N - i; # Atleast K stars are found if (sum >= K): ans = i; break; # Print Answer print(ans); # Driver Code if __name__ == '__main__': N = 3; K = 8; get(N, K); # This code is contributed by 29AjayKumar
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the index of
// required row
static void get(int N, int K)
{
// Stores the count of stars
// till ith row
int sum = 0, ans = 0;
// Iterating over the rows
for (int i = 1; i <= 2 * N - 1; i++) {
// Upper half
if (i <= N) {
sum += i;
}
// Lower half
else {
sum += 2 * N - i;
}
// Atleast K stars are found
if (sum >= K) {
ans = i;
break;
}
}
// Print Answer
Console.Write(ans +"\n");
}
// Driver Code
public static void Main(String[] args)
{
int N = 3, K = 8;
get(N, K);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to find the index of
// required row
function get(N, K)
{
// Stores the count of stars
// till ith row
let sum = 0, ans;
// Iterating over the rows
for (let i = 1; i <= 2 * N - 1; i++) {
// Upper half
if (i <= N) {
sum += i;
}
// Lower half
else {
sum += 2 * N - i;
}
// Atleast K stars are found
if (sum >= K) {
ans = i;
break;
}
}
// Print Answer
document.write(ans);
}
// Driver Code
let N = 3, K = 8;
get(N, K);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
4
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante la búsqueda binaria en el valor del número de filas de [0, 2*n-1] . Siga los pasos a continuación para resolver el problema:
- Inicialice las variables start = 0, end = (2 * N) – 1 y, ans = 0.
- Siga estos pasos mientras el valor del inicio sea menor que el final .
- Calcular mid que es igual a (start + end) / 2
- Cuenta el número de estrellas hasta la mitad .
- Si el número de estrellas hasta la mitad es mayor o igual a K, guarde la mitad en la variable y muévase hacia la izquierda de la mitad por fin = mitad-1
- De lo contrario, muévase a la derecha de mid by start = mid+1
- Retorna ans cuál es el valor requerido.
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 count the number of rows
int count_rows(int n, int k)
{
// A diamond pattern contains
// 2*n-1 rows so end = 2*n-1
int start = 1, end = 2 * n - 1, ans = 0;
// Loop for the binary search
while (start <= end) {
int mid = start - (start - end) / 2;
int stars_till_mid = 0;
if (mid > n) {
// l_stars is no of rows in
// lower triangle of diamond
int l_stars = 2 * n - 1 - mid;
int till_half = (n * (n + 1)) / 2;
stars_till_mid
= till_half + ((n - 1) * (n)) / 2
- ((l_stars) * (l_stars + 1)) / 2;
}
else {
// No of stars till mid th row
stars_till_mid = mid * (mid + 1) / 2;
}
// Check if k > starts_till_mid
if (k <= stars_till_mid) {
ans = mid;
end = mid - 1;
}
else
start = mid + 1;
}
// Return Answer
return ans;
}
// Driver function
int main()
{
int N = 3, K = 8;
// Call the function
// and print the answer
cout << count_rows(N, K);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count the number of rows
static int count_rows(int n, int k)
{
// A diamond pattern contains
// 2*n-1 rows so end = 2*n-1
int start = 1, end = 2 * n - 1, ans = 0;
// Loop for the binary search
while (start <= end) {
int mid = start - (start - end) / 2;
int stars_till_mid = 0;
if (mid > n) {
// l_stars is no of rows in
// lower triangle of diamond
int l_stars = 2 * n - 1 - mid;
int till_half = (n * (n + 1)) / 2;
stars_till_mid
= till_half + ((n - 1) * (n)) / 2
- ((l_stars) * (l_stars + 1)) / 2;
}
else {
// No of stars till mid th row
stars_till_mid = mid * (mid + 1) / 2;
}
// Check if k > starts_till_mid
if (k <= stars_till_mid) {
ans = mid;
end = mid - 1;
}
else
start = mid + 1;
}
// Return Answer
return ans;
}
// Driver function
public static void main(String[] args)
{
int N = 3, K = 8;
// Call the function
// and print the answer
System.out.print(count_rows(N, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# python3 program for the above approach # Function to count the number of rows def count_rows(n, k): # A diamond pattern contains # 2*n-1 rows so end = 2*n-1 start = 1 end = 2 * n - 1 ans = 0 # Loop for the binary search while (start <= end): mid = start - (start - end) // 2 stars_till_mid = 0 if (mid > n): # l_stars is no of rows in # lower triangle of diamond l_stars = 2 * n - 1 - mid till_half = (n * (n + 1)) / 2 stars_till_mid = till_half + \ ((n - 1) * (n)) / 2 - ((l_stars) * (l_stars + 1)) / 2 else: # No of stars till mid th row stars_till_mid = mid * (mid + 1) / 2 # Check if k > starts_till_mid if (k <= stars_till_mid): ans = mid end = mid - 1 else: start = mid + 1 # Return Answer return ans # Driver function if __name__ == "__main__": N = 3 K = 8 # Call the function # and print the answer print(count_rows(N, K)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG{
// Function to count the number of rows
static int count_rows(int n, int k)
{
// A diamond pattern contains
// 2*n-1 rows so end = 2*n-1
int start = 1, end = 2 * n - 1, ans = 0;
// Loop for the binary search
while (start <= end) {
int mid = start - (start - end) / 2;
int stars_till_mid = 0;
if (mid > n) {
// l_stars is no of rows in
// lower triangle of diamond
int l_stars = 2 * n - 1 - mid;
int till_half = (n * (n + 1)) / 2;
stars_till_mid
= till_half + ((n - 1) * (n)) / 2
- ((l_stars) * (l_stars + 1)) / 2;
}
else {
// No of stars till mid th row
stars_till_mid = mid * (mid + 1) / 2;
}
// Check if k > starts_till_mid
if (k <= stars_till_mid) {
ans = mid;
end = mid - 1;
}
else
start = mid + 1;
}
// Return Answer
return ans;
}
// Driver function
public static void Main()
{
int N = 3, K = 8;
// Call the function
// and print the answer
Console.Write(count_rows(N, K));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript program for the above approach
// Function to count the number of rows
const count_rows = (n, k) => {
// A diamond pattern contains
// 2*n-1 rows so end = 2*n-1
let start = 1, end = 2 * n - 1, ans = 0;
// Loop for the binary search
while (start <= end)
{
let mid = start - parseInt((start - end) / 2);
let stars_till_mid = 0;
if (mid > n)
{
// l_stars is no of rows in
// lower triangle of diamond
let l_stars = 2 * n - 1 - mid;
let till_half = (n * (n + 1)) / 2;
stars_till_mid = till_half + ((n - 1) * (n)) / 2 -
((l_stars) * (l_stars + 1)) / 2;
}
else
{
// No of stars till mid th row
stars_till_mid = mid * (mid + 1) / 2;
}
// Check if k > starts_till_mid
if (k <= stars_till_mid)
{
ans = mid;
end = mid - 1;
}
else
start = mid + 1;
}
// Return Answer
return ans;
}
// Driver code
let N = 3, K = 8;
// Call the function
// and print the answer
document.write(count_rows(N, K));
// This code is contributed by rakeshsahni
</script>
Producción
4
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA