Given two integers N and K, where N represents a diamond pattern with (2 * N) -1 rows, the task is to find the index of the first row up to which there are at least K stars in a diamond pattern.
Please note that the value of K will always have a definite answer.
Examples:
Input: N = 3 , K = 8
Output: 4
Explanation: The first 4 rows contain a total of 8 stars.
** *
* * *
* *
*
Input: N = 5, K = 5
Output: 3
Naive Approach: The given problem can be solved by simply iterating over each row and maintaining the count of the number of stars in each row. Print the first two where the count of stars exceeds K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the index of// required rowvoid 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 Codeint main(){ int N = 3, K = 8; get(N, K); return 0;} |
Java
// Java program for the above approachimport 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 rowdef 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 Codeif __name__ == '__main__': N = 3; K = 8; get(N, K);# This code is contributed by 29AjayKumar |
C#
// C# program for the above approachusing 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 rowfunction 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 Codelet N = 3, K = 8;get(N, K);// This code is contributed by saurabh_jaiswal.</script> |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized using binary search on the value of the number of rows from [0, 2*n-1]. Follow the steps below to solve the problem:
- Initialize variables start = 0, end = (2 * N) – 1 and, ans = 0.
- Follow these steps while the value of the start is less than the end.
- Calculate mid which is equal to (start + end) / 2
- Count the number of stars till mid.
- If the number of stars till mid are greater than or equal to K, store the mid into the variable and move towards the left of mid by end = mid-1
- Else, move right of mid by start = mid+1
- Return ans which is the required value.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of rowsint 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 functionint main(){ int N = 3, K = 8; // Call the function // and print the answer cout << count_rows(N, K);} |
Java
// Java program for the above approachimport 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 rowsdef 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 functionif __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 approachusing 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 rowsconst 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 codelet N = 3, K = 8;// Call the function// and print the answerdocument.write(count_rows(N, K));// This code is contributed by rakeshsahni</script> |
Output
4
Time Complexity: O(log N)
Auxiliary Space: O(1)
Take a part in the ongoing discussion
