Given a line. At each level, that line can be divided into either two new lines or end up with a circle at its edge. An array X[] of size N is given to you, in which each X[i] denotes the number of circles at the ith level for (1? i ? N). Then you must determine whether X[] meets the above condition and return VALID or NOT VALID.
Examples:
Input: N = 4, X[] = {0, 0, 3, 2}
Output: VALID
Explanation:
Example 1
- At Level 1 the line is divided into 2 new lines for Level 2. Therefore, the number of circles at Level 1 = 0.
- At Level 2 both the two lines were divided into two new lines to form a total of 4 lines for Level 3. Therefore, the number of circles at Level 2 = 0.
- At Level 3, 3 lines ended up with circles on its edge, and one line was divided into two new lines for Level 4. Therefore, the number of circles at Level 3 = 3.
- At Level 4, Both the lines ended up with circles on their edge. Therefore, the number of circles at Level 4 = 2.
The circles from levels 1 to 4 are 0, 0, 3 and 2 respectively, Which are the same as X[i] for (1 <= i <= N). Therefore, X[] is VALID.
Input: N = 3, X[] = {1, 2, 3}
Output: NOT VALID
Explanation: It can be verified that the given X[] is not valid according to the given condition in the statement.
Approach: Implement the idea below to solve the problem:
The problem is observation based and can be solved by using some mathematics.
Steps were taken to solve the problem:
- Create two variables ST and LE and initialize them equal to 1 and 0 respectively.
- Run a loop from i = 0 to less than N and follow the below-mentioned steps under the scope of the loop:
- If (ST < 0) return NOT VALID.
- If (X[i] == 0) ST *= 2
- else:
- If(X[i] > ST) then return NOT VALID
- ST -= X[i]
- ST *= 2
- If (ST != 0) then return NOT VALID else return VALID
Below is the code to implement the above approach:
C++
//C++ code for the above approach#include <iostream>using namespace std;// Function to check whether the array// is validstring Is_Valid(int X[], int N){ int st = 1; int le = 0; for (int i = 0; i < N; i++) { if (st < 0) return "NOT VALID"; if (X[i] == 0) { st = st * 2; } else { // If number of circles // cross st if (X[i] > st) return "NOT VALID"; st -= X[i]; st = st * 2; } } // If St is not equal to zero if (st != 0) return "NOT VALID"; return "VALID";}// Driver codeint main(){ int N = 5; int X[] = { 0, 1, 0, 3, 2 }; // Function call cout << Is_Valid(X, N); return 0;}//This code is contributed by Potta Lokesh |
Java
// Java Implementation of the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Function to check whether the array // is valid public static String Is_Valid(int[] X, int N) { int st = 1; int le = 0; for (int i = 0; i < N; i++) { if (st < 0) return "NOT VALID"; if (X[i] == 0) { st = st * 2; } else { // If number of circles // cross st if (X[i] > st) return "NOT VALID"; st -= X[i]; st = st * 2; } } // If St is not equal to zero if (st != 0) return "NOT VALID"; return "VALID"; } // Driver code public static void main(String[] args) throws java.lang.Exception { int N = 5; int[] X = { 0, 1, 0, 3, 2 }; // Function call System.out.println(Is_Valid(X, N)); }} |
Javascript
//Javascript code for the above approach// Function to check whether the array// is validfunction Is_Valid(X, N){ let st = 1; let le = 0; for (let i = 0; i < N; i++) { if (st < 0) return "NOT VALID"; if (X[i] == 0) { st = st * 2; } else { // If number of circles // cross st if (X[i] > st) return "NOT VALID"; st -= X[i]; st = st * 2; } } // If St is not equal to zero if (st != 0) return "NOT VALID"; return "VALID";}// Driver codelet N = 5;let X = [ 0, 1, 0, 3, 2 ];// Function callconsole.log(Is_Valid(X, N)); |
Python3
import sysclass main(object): n = 3 X = [0, 0, 4] nob = 1 found = True i = 0 while i < n: if X[i] > nob: found = False break nob = nob - X[i] nob = nob * 2 i += 1 if found and nob == 0: print("VALID") else: print("NOT VALID") |
C#
using System;class Program{ // Function to check whether the array is valid static string Is_Valid(int[] X, int N) { int st = 1; int le = 0; // Loop through each element in the array for (int i = 0; i < N; i++) { // If the number of sticks is negative, return "NOT VALID" if (st < 0) return "NOT VALID"; if (X[i] == 0) { // Multiply the number of sticks by 2 if the element is 0 st = st * 2; } else { // If number of circles crosses the number of sticks, return "NOT VALID" if (X[i] > st) return "NOT VALID"; // Deduct the number of circles from the number of sticks st -= X[i]; // Multiply the number of sticks by 2 st = st * 2; } } // If the number of sticks is not equal to zero, return "NOT VALID" if (st != 0) return "NOT VALID"; // Return "VALID" if the array is valid return "VALID"; } static void Main(string[] args) { int N = 5; int[] X = { 0, 1, 0, 3, 2 }; // Call the Is_Valid function and print the result Console.WriteLine(Is_Valid(X, N)); }} |
Output
VALID
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
