I hate Even Subarrays (HACKEREARTH)

 You are given a binary string, (string which contains 0's and 1's), You have to perform several operations on this string, in one operation choose a non-empty even length substring containing only 0's or only 1's and remove it from the string.

Your goal is to minimize the final length of the string after performing several operations.It is possible that the final string may become empty, in that case print "KHALI" without quotes.

And it can be proved that there is always an unique string with minimal length after performing the operations.

Input:

  • First line of input contains an intger T denoting number of testcases.
  • Next T lines of input contains a binary string S.

Output:

  • for each testcase print the required minimal string.

Constraints:

  • 1 <= T <= 10
  • 1 <= |S|  <= 105

 

SAMPLE INPUT
 
2
101001
1001
SAMPLE OUTPUT
 
10
KHALI
Explanation

for the first test case, first remove substring "00", now string will become "1011", now remove "11", hence "10" will be the resulting string.



SOLUTION:


for _ in range(int(input())):

arr = [int(i) for i in input()]

stack = []

for i in arr:

if len(stack) > 0 and i == stack[0]:

stack.pop(0)

else:

stack.insert(0, i)

stack.reverse()

if len(stack) == 0:

print('KHALI')

else:

for i in stack:

print(i, end = '')

print()

Comments

Post a Comment

Popular posts from this blog

Short Notes Of computer Network

Image
  OSI Layers,data units and Functions: Layers Data Units Functions Application Layer Data Mail Services,Directory Serices,FTAM Presentation Layer Data Encryption/Decryption, Compression Session Layer Data Session Establishment, Synchronization,Dialog Controller Transport Layer Segments,Datagram Segementation Network Layer Packets Traffic control,Fragmentation,Routing Data Link Layer Frames Flow control,Error control,Access control Physical Layer Bits Bit Synchronization,Bit rate control,Physical Topologies Layers and their uses – Physical Layer Network Topologies: Mesh Topology: In mesh topology, every device is connected to another device via particular channel.If suppose, N number of devices are connected with each other, then total number of links required to connect NC 2 . Bus Topology: Bus topology is a network type in which every computer and network device is connected to single cable. If N devices are connected, then the number of cables required 1 which is known as backbone ca
Read more

Short Note of Data Structure

  Arrays   An array is collection of items stored at continuous memory locations. The idea is to declare multiple items of same type together.  Array declaration:  In C, we can declare an array by specifying its and size or by initializing it or by both. // Array declaration by specifying size int arr[10]; // Array declaration by initializing elements int arr[] = {10, 20, 30, 40}; // Array declaration by specifying size and // initializing elements int arr[6] = {10, 20, 30, 40} Formulas:    Length of Array = UB - LB + 1 Given the address of first element, address of any other element is calculated using the formula:- Loc (arr [k]) = base (arr) + w * k w = number of bytes per storage location of for one element k = index of array whose address we want to calculate Elements of two-dimensional arrays ( mXn ) are stored in two ways:- Column major order: Elements are stored column by column, i.e. all elements of first column are stored, and then all elements of
Read more

Sort in specific order (GFG)

  Given an array   A   of positive integers. Your task is to sort them in such a way that the first part of the array contains odd numbers sorted in descending order, rest portion contains even numbers sorted in ascending order. Input: The first line of input contains an integer  T  denoting the number of test cases. Then  T  test cases follow. Each test case contains an integer  N  denoting the size of the array. The next line contains  N  space separated values of the array. Output: For each test case in a new line print the space separated values of the modified array. Constraints: 1 <= T <= 10 3 1 <= N <= 10 7 0 <= A i  <= 10 18 Example: Input: 2 7 1 2 3 5 4 7 10 7 0 4 5 3 7 2 1 Output: 7 5 3 1 2 4 10 7 5 3 1 0 2 4 Explanation: Testcase1:  Array elements 7 5 3 1 are odd and sorted in descending order, whereas 2 4 10 are even numbers and sorted in ascending order. SOLUTION: t=int(input()) for i in range (t):     n=int(input())     p=list(map(int,input().split()))  
Read more