## UVA Problem 11965 – Extra Spaces Solution

UVA Problem 11965 – Extra Spaces Solution:

Solving Technique:

This problem is very straightforward. We just need to skip outputting consecutive spaces. Instead of multiple spaces only print one space.

The only problem for this problem may be outputting a blank line between test cases. This can be handled in many ways. I have shown one method below. I have commented the code below, have a look.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Critical Input:

```4
3
Sample test one:
there was     2 spaces and
here are also  2  spaces
2
Sample test two:
there was 4 spaces
3
Sample         test one:
there was 2 spaces and
here are also  2    spaces
2
Sample test two:
there was 4 spaces
```

Output:

```Case 1:
Sample test one:
there was 2 spaces and
here are also 2 spaces

Case 2:
Sample test two:
there was 4 spaces

Case 3:
Sample test one:
there was 2 spaces and
here are also 2 spaces

Case 4:
Sample test two:
there was 4 spaces```

### Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<cstdio>

static char buffer[1024];

int main(){
register unsigned int n, m, c = 0;
scanf("%u", &n);

while (n--){

/*
* Use getchar() before reading a string or character to discard the newline character,
* Otherwise newline character will be taken taken by the string or character input function
*/
scanf("%u", &m); getchar();

/*
* Only print newline between test cases
*/
if (c) printf("\n");

++c;
printf("Case %u:\n", c);

while (m--){
gets(buffer);

register unsigned i = 0, spaces = 1;
unsigned val;

for (; val = buffer[i]; ++i){

/*
* Cutting Comparison
* @example use this code {{ val = val == ' ' }}
* replace {{ val == ' ' }} statements with just {{ val }}
*/

/*
* If a space found after non space character then print a space
*/
if (val == ' ' && spaces){
printf(" ");
spaces = 0;
continue;
}

/*
* If consecutive space are found skip them
*/
if (val == ' ') continue;

/*
* Print non space characters
*/
printf("%c", buffer[i]);
spaces = 1;
}
printf("\n");
}
}
return 0;
}
```

## UVA Problem 10041 – Vito’s Family Solution

UVA Problem 10041 – Vito’s Family Solution:

Solving Technique:

This is a sorting problem. It requires us minimize the distance from Vito’s to every other house. That distance must be median because median value minimizes the distance from every side. So the median is the position of Vito’s house.

The problem requires us to find, “minimal sum of distances from the optimal Vito’s house to each one of his relatives”. So this means we calculate distance from Vito’s house ( Median ) to every other house and sum them. Meaning subtract position of every house from Vito’s house and sum their distance.

I have provided Three commented codes below. First one uses STL Sort and doesn’t calculate absolute value for distance. Second one shows the use of Insertion Sort and calculates absolute value to find their distance. The last one uses vector to store data and STL algorithm to find nth element in an array. Here ( for this code ) the calculated nth element is the median.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```2
2 2 4
3 2 4 6```

Output:

```2
4```

### Code ( Without Calculating Absolute Value ):

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<cstdio>
#include<algorithm>

static int A[512];

int main(){
register int n, m, i, j;
scanf("%d", &n);

while (n--){
scanf("%d", &m);

if (m == 1){
/**
* If only 1 input then no need to process
* For 1 input the distance is always Zero
*/
scanf("%*d");
printf("0\n");
}

else{
int dist = 0, median, key;

for (i = 0; i < m; ++i)
scanf("%d", &A[i]);

/**
* Sort the input using stl sort
* Instead of using sorting algorithm, Try to implement Selection Algorithm to find Median in O(n) time
*/
std::sort(A, A + m);

/**
* Find median dividing by two or shifting bit to left once
* here, key is the value of median
*/
median = m >> 1;
key = A[median];

/**
* here, dist is the summation of distance of every house
* Any value less than Median can subtracted from median will result in a positive value
*/
for (i = 0; i< median; ++i)
dist += key - A[i];

/**
* No need calculate for the median so start from (median + 1)
* In case of value greater than Median, the Median must be subtracted from that value for positive number
* Also by removing duplicates of median we may speed up the code
*/
for (i = median + 1; i < m; ++i)
dist += A[i] - key;

printf("%d\n", dist);
}
}
return 0;
}
```

### Code ( Insertion Sort ):

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<stdio.h>
#include<stdlib.h>

static int A[512];

int main(){
register int n,m,i,j;
scanf("%d", &n);

while (n--){
scanf("%d", &m);
int dist = 0, median, key;

for (i = 0; i < m; ++i){
scanf("%d", &A[i]);
}

/**
* Insertion Sort:
* Two portions sorted and unsorted
*/
for (i = 1; i < m; ++i){
key = A[i];
j = i - 1;

/**
* Compare every element with sorted portion ( elements to its left )
*/
while (j >= 0 && A[j] > key){

/**
* While comparing shift items to right until the comparison is false
*/
A[j + 1] = A[j];
--j;
}

/**
* When comparison is False or done, we found the sorted position for that element so we insert it in that position
*/
A[j + 1] = key;
}

/**
* Find Median value, left shift once is divided by Two
*/
key = A[m >> 1];

/**
* Since elements after Median is bigger than Median So, we need to find absolute value of them
*/
for (i = 0; i < m; ++i){
dist += abs(key - A[i]);
}

printf("%d\n", dist);
}
return 0;
}
```

### Code ( using vector & n-th element to find median ):

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>

using namespace std;

int main(){
register int n, m, i, j;
int key, num;
vector<int> v;

scanf("%d", &n);
while (n--){
scanf("%d", &m);

if (m == 1){
/**
* If only 1 input then no need to process
* For 1 input the distance is always Zero
*/
scanf("%*d");
printf("0\n");
}

else{
/**
* Input an a value and push it to vector
*/
v.clear();
for (i = 0; i < m; ++i){
scanf("%d", &num);
v.push_back(num);
}

/**
* sort for median
*/
nth_element(v.begin(), v.begin() + v.size()/2, v.end());

/**
* Get the value of median
*/
key = v[v.size()/2];

/**
* Get distance of every value from median
*/
int dist = 0;
for (j = 0; j < i; ++j)
dist += abs(key - v[j]);

printf("%d\n", dist);

}
}
return 0;
}
```

## UVA Problem 10347 – Medians Solution

UVA Problem 10347 – Medians Solution:

Solving Technique:

This is a simple geometrical problem. We can use Heron’s formula to calculate the area.

Use double for safety. Print 3 places after decimal point. If the area is invalid then print -1.000 ( with 3 Zeros ) after decimal point. This may be a reason for WA.

I have provided two codes. One of them uses fread and string stream ( include sstream ) to take and process input. I have commented this code for easier understanding. The other code is with out fread, stringstream and not commented.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Critical Inputs:

``` 1  2  3
5  9  4
3  2  3
4  5  3
-3 -3 -3```

Output:

```-1.000
-1.000
3.771
8.000
5.196```

### Code:

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>

static char buffer[32768];

int main(){
double a,b,c,s;

/**
* @brief Read file from stdin and create string stream of buffer
*/
std::stringstream ss(buffer);

while (ss >> a >> b >> c){

/**
* Heron's Formula: s, is semi perimeter
*/
s = (a + b + c) / 2.0;

/**
* Heron's Formula: area, of a triangle
*/
double area = (4.0 / 3.0) * sqrt(s * (s - a) * (s - b) * (s - c));

/**
* If area is not valid then print -1, otherwise print area
*/
area > 0 ? printf("%0.3lf\n", area) : printf("-1.000\n");
}
return 0;
}
```

### Code ( Without fread() and stringstream() ):

```/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<iostream>
#include<cstdio>
#include<sstream>
#include<cmath>

using namespace std;

int main(){
double a,b,c,s;

while (scanf("%lf%lf%lf", &a, &b, &c) == 3){

double s = (a + b + c) / 2.0;
double area = (4.0 / 3.0) * sqrt(s * (s - a) * (s - b) * (s - c));

if(area > 0)
printf("%0.3lf\n", area);
else
printf("-1.000\n");

}
return 0;
}
```

## UVA Problem 11462 – Age Sort Solution

UVA Problem 11462 – Age Sort Solution:

Solving Technique:

First of all a warning. This is going to be a very very very long post. For this problem i will use various divide and conquer algorithms ( Ex: quick sort, merge sort etc ) & techniques to solve.

The best Solution here takes 0.502 s ( 502 ms ) . If you are looking for a very fast solution this is not the right place. But these code can be optimized to create a very fast solution.  Also sorts such as bubble sort, selection sort, insertion sort, replacement sort won’t be able to sort in time. So you’ll get TLE if you use these sort.

#### Lets begin:

This is a sorting problem. The only trouble here is the huge count of test cases. But there’s very important line most miss including me. That is ” no individual in that country lives for 100 or more years “. So we may have many many test cases but no input age is more than 100. 🙂

Now lets look at our solution menu,

1. Counting sort ( Just count occurrence of each values, then print them 0 to 100 for ascending order).

2. Binary Merge sort ( 2 partition ).

3. Ternary Merge sort ( 3 partition ).

4. Quick sort ( 2 partition ).

5. Quick sort ( 3 partition ).

The first solution code here ( counting sort ) runs the fastest since it just count elements at each index and prints them. This solution may be made faster by using combination of fread, fwrite, strtok, atoi, stringstream ( <sstream> ) . Although i haven’t used them. If i get time I will try to implement them in future.

I used the other sorts here just demonstrate implementation of merge sort and quick sort algorithms. I may include more sorting algorithms for this problem in future. All codes are well commented take a look below and try to understand their logic.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Input:

```5
3 4 2 1 5
5
2 3 2 3 1
0```

Output:

```1 2 3 4 5
1 2 2 3 3```

#### Counting Sort Code:

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 11462 ( Age sort )
* Solution Method: Counting Sort
*/

#include<stdio.h>
#include<string.h>

static unsigned A[128];

int main(){
register unsigned n, i, c;
unsigned num;
while(scanf("%u", &n) && n){             /* Test cases */
memset(A, 0, sizeof A);              /* Clear memory for each test case */
for(i = n; i; --i){                  /* Exits Loop when i is 0 */
scanf("%u", &num);
++A[num];                        /* Since input is never greater than 100, we can use that as index and count occurrence of that index */
}
c = i = 1;                           /* i starts from 1 since i is never 0  */
for(; i<100; ++i){
while(A[i]--){                   /* Decrease number count at that index */
if(c == n) printf("%u", i);  /* For the last item in sorted output there is no space */
else{
printf("%u ", i);        /* Just print the index since that was our original input */
++c;                     /* Counter to check if the last element is reached */
}
}
}
printf("\n");                        /* Print a new line for each test case */
}
return 0;
}
```

#### Counting Sort Code ( Usage of stringstream, *slower ):

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 11462 ( Age sort )
* Description: stringstream demo
*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<sstream>

using namespace std;

static unsigned A[128];

int main(){
register unsigned n, c, i;
unsigned num;
string B;
while(1){
scanf("%u", &n); getchar();
if(!n) return 0;

memset(A, 0, sizeof A);
getline(cin, B);

stringstream ss;
ss << B;
while(ss >> num)
++A[num];

c = i = 1;
for(; i < 100; ++i){
while(A[i]--){
if(c == n) printf("%u", i);
else{
printf("%u ", i);
++c;
}
}
}
printf("\n");
}
return 0;
}
```

#### Binary Merge Sort Code ( 2 Partition ):

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 11462 ( Age sort )
* Solution Method: Binary Merge Sort ( 2 Partition )
*/

#include<stdio.h>
#include<limits.h>

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid, register unsigned rear){
register unsigned n1 = mid-front+1;         /* Calculate size of left half of the array */
register unsigned n2 = rear - mid;          /* Calculate size of right half of the array */

unsigned *L = new unsigned[n1 + 1];     /* Dynamically create and allocate calculated amount of memory */
unsigned *R = new unsigned[n2 + 1];     /* plus 1 to hold Infinity or A Very large value for which any input can't be larger than */

register unsigned i = 0;
for(; i < n1; ++i)
L[i] = A[front+i];                          /* Copy elements from given original array to left sub array */

register unsigned j = 0;
for(; j < n2; ++j)
R[j] = A[mid + 1 + j];                          /* Copy elements from given original array to right sub array */

L[n1] = INT_MAX;                                /* In the last position of sub array set a very large value */
R[n2] = INT_MAX;
i = j = 0;

register unsigned k = front;                /* Instead of wasting space creating a new array, we can use the original large array since we have already copied all items to sub arrays */
for(; k <= rear; ++k){
if(L[i] <= R[j])
A[k] = L[i++];             /* Compare and copy smaller elements of sub arrays onto original array */
else
A[k] = R[j++];
}
}

void Mergesort(register unsigned front, register unsigned rear){
if(front < rear){
register unsigned mid = (rear+front) >> 1;  /* Find the mid point of the array */
/* Shift bits to right once, equivalent of divided by TWO */

Mergesort(front, mid);                       /* Recursively divide array in left portion */
Mergesort(mid+1, rear);                      /* Recursively divide array in right portion */

Merge(front, mid, rear);                     /* Merge the divided array back again in sorted order */
}
}

int main(){
register unsigned n, i;
while(scanf("%u", &n) && n){
for(i=0; i<n; ++i)
scanf("%u", &A[i]);

Mergesort(0, n-1);                          /* Call merge sort function for each test case */

for(i = 0; i<n; ++i){
printf("%u", A[i]);
if(i != n - 1)
printf(" ");                 /* Do not print a space after last sorted item */
}
printf("\n");
}
return 0;
}
```

#### Ternary Merge Sort Code ( 3 Partition ):

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 11462 ( Age sort )
* Solution Method: Ternary Merge Sort ( 3 Partition )
*/

#include<stdio.h>
#include<limits.h>

#define SIZE 2000002
static unsigned A[SIZE];

void Merge(register unsigned front, register unsigned mid1, register unsigned mid2, register unsigned rear){
/*
* Calculate size for creating sub array
* In this case calculate size for three sub arrays
*/
unsigned n1 = mid1 - front + 1;
unsigned n2 = mid2 - mid1;
unsigned n3 = rear - mid2;

/*
* Dynamically allocate memory for three sub arrays
* Here Plus One because we will set a very large value for last position of the array
*/
unsigned *L = new unsigned[n1 + 1];
unsigned *R = new unsigned[n2 + 1];
unsigned *X = new unsigned[n3 + 1];

/*
* Copy 1/3 of original array to sub arrays
* First 1/3 to L array, next 1/3 to R array, last 1/3 to X array
*/
register  int i = 0;
for(; i<n1; ++i)
L[i] = A[front + i];

for(i=0; i<n2; ++i)
R[i] = A[mid1 + 1 + i];

for(i = 0; i < n3; ++i)
X[i] = A[mid2 + 1 + i];

/*
* INT_MAX is found in <limits.h>
* Instead of traversing the whole array increasing runtime
* We can compare every element again a very large value which will always be grater than or equal to any input
*/
L[n1] = INT_MAX;
R[n2] = INT_MAX;
X[n3] = INT_MAX;

/*
* Reset index counter for sorting
*/
i = 0;
register unsigned p = 0, j = 0, k = front;

/*
* Sort:
* Compare items of each array against each other
* Copy back the smaller item from the comparison to original array
*/
for(; k <= rear; ++k){
if(L[i] <= R[j] && L[i] <= X[p]){
A[k] = L[i];
++i;
}else if(R[j] <= X[p]){
A[k] = R[j];
++j;
}else{
A[k] = X[p];
++p;
}
}
}

void Mergesort(register int front, register int rear){
/*
* Check if there is only One element in array
*/
if(front < rear){
/*
* calculate the size of 1/3 of array
* Now calculate two mid points since it is 3 way partition
*/
register int dist = (rear - front + 1) / 3;
int mid1 = front + dist;
int mid2 = mid1 + dist;

/*
* Recursively call this array cutting down original array by 1/3 ( One Third )
*/
Mergesort(front, mid1);
Mergesort(mid1 + 1, mid2);
Mergesort(mid2 + 1, rear);

/*
* Merge divided elements back into original array
*/
Merge(front, mid1, mid2, rear);
}
}

int main(){
register int n, i;
while(scanf("%u", &n) && n){
for(i = 0; i < n; ++i)
scanf("%u", &A[i]);

/*
* Merge sort from index 0 to index n-1
*/
Mergesort(0, n - 1);

for(i = 0; i < n; ++i){
printf("%u", A[i]);
/*
* For the last sorted element do not print a space
*/
if(i != n-1)
printf(" ");
}
printf("\n");
}
return 0;
}
```

#### Quick Sort Code ( 2 Partition ):

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 11462 ( Age sort )
* Solution Method: Quick Sort ( 2 Partition )
*/
#include<cstdio>
#include<iostream>

#define SIZE 2000002

static int A[SIZE];

void quicksort (int *a, register int n) {
register int i, j, mid;
if (n < 2) return;

mid = a[n >> 1];

for (i = 0, j = n - 1; ; i++, j--) {
while (a[i] < mid)
i++;
while (mid < a[j])
j--;

if (i >= j) break;
std::swap(a[i], a[j]);
}
quicksort(a, i);
quicksort(a + i, n - i);
}

int main () {
register unsigned n, i;
while(scanf("%u", &n) && n){
for(i = 0; i < n; ++i)
scanf("%d", &A[i]);

quicksort(A, n);

for (i = 0; i < n; i++)
printf("%d%s", A[i], i == n - 1 ? "\n" : " ");

}
return 0;
}
```

#### Quick Sort Code ( 3 Partition ):

```/* To Do */
```

## Digital Logic AND Gate with C Bitwise Operations

#### Digital Logic AND Gate with C Bitwise Operations:

##### AND Logic:

A, B is input, Q is output,

`A . B = Q  /* AND is represented by dot ( . ) */`

AND Truth Table,

```A  B     Q (A . B)
==========
0  0     0
0  1     0
1  0     0
1  1     1
```

##### C Code:
`In C, C++ AND bit wise AND can be performed using &( Ampersand )`

Don’t confuse single logical AND ( Double Ampersand && ) with bitwise AND ( Single Ampersand & ).

```printf("%d\n", 5 & 6 );    /* Output 4  */
printf("%d\n", 8 & 4 );    /* Output 0  */
printf("%d\n", 54 & 29);   /* Output 20 */
```

##### Code Explanation:

Bit wise AND takes two binary digits of same length and performs AND operation on corresponding bits of first and second number. If both bits are 1 then result is 1, otherwise result is 0. Use the table given above.

```5 & 6 = 4,

0101 # 5        /* 0 + 4 + 0 + 1 = 5 */
0110 # 6        /* 0 + 4 + 2 + 0 = 6 */
=========
0100 # 4        /* 0 + 4 + 0 + 0 = 4 */
```

```8 & 4 = 0,

1000 # 8        /* 8 + 0 + 0 + 0 = 8 */
0100 # 4        /* 0 + 4 + 0 + 0 = 4 */
=========
0000 # 0        /* 0 + 0 + 0 + 0 = 0 */
```

```54 & 29 = 20,

0011 0110 # 54  /* 0 + 0 + 32 + 16 + 0 + 4 + 2 + 0 = 54 */
0001 1101 # 29  /* 0 + 0 +  0 + 16 + 8 + 4 + 0 + 1 = 29 */
==============
0001 0100 # 20  /* 0 + 0 +  0 + 16 + 0 + 4 + 0 + 0 = 20 */
```

## Decimal Number Representation in Binary ( Binary to Decimal Explanation )

##### Decimal Number Representation in Binary ( Binary to Decimal Explanation ):

Binary means base-2 number system. There are only two symbols 0 ( Zero ) and 1 ( One ). Each Binary Digit is called bit. Calculating decimal equivalent of binary number is easy. Index is always from bit Count Minus One to Zero.

We start raising two to the power 0 from the right most bit and increment for each left bit. Another way is we start from right raising two to the power of bit length – 1 and decrement for every right bit.

Our base is two. Whenever we find a 1 in binary number we raise its index to power of 2 and sum all those numbers. See example below,

5 in 3 bit binary is, 101

```0  1  0  1
23 22 21 20
0  4  0  1   /* summing these gives us 5 */
```

54 in 6 bit binary is, 110110

```1   1   0   1  1  0
25  24  23  22  21 20
32  16  0   4  2  0   /* summing these gives 54 */
```

###### Extras,

Bit pattern count = 2bit
8 bit = 1 Byte

Byte is represented by Capital B while bit is represented by small b.
MB = Megabyte
Mb = Megabit

## Basic Gate IC’s

#### Basic IC’s ( Integrated Circuits ):

Basic Integrated Circuits:

74LS00 – Quad 2 input NAND Gate
74LS02 – Quad 2 input NOR Gate
74LS04 – 1 input NOT Gate ( Hex Inverter )
74LS08 – Quad 2 input AND Gate
74LS32 – Quad 2 input OR Gate
74LS86 – Quad 2 input XOR

## CodeEval Easy Level Challenge Lowercase

CodeEval Easy Level Challenge Lowercase:

##### Description:

For this problem we just need to change upper case letters to lower case. Here i have solved this problem in 4 programming languages c, c++, java, python.

##### C:
```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

#include <stdio.h>
int main(int argc, const char * argv[]) {
FILE *file = fopen(argv[1], "r");
char line[1024];
while (fgets(line, 1024, file)) {
for(register unsigned int i=0; line[i]; ++i){
if(line[i] >= 'A' && line[i]<='Z') printf("%c", line[i]+32);
else printf("%c", line[i]);
}
printf("\n");
}
return 0;
}
```

##### Java:
```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

import java.io.*;
public class Main {
public static void main (String[] args) throws IOException {
File file = new File(args[0]);
String line;
while ((line = buffer.readLine()) != null) {
line = line.trim();
// Instead of changing case one by one in for loop, we can also change case of whole string in one function call
/* System.out.println(line.toLowerCase()); */
for(int i=0; i<line.length(); ++i){
char c = line.charAt(i);
if(Character.isUpperCase(c)) System.out.print(Character.toLowerCase(c));
else System.out.print(c);
}
System.out.println();
}
}
}
```

##### Python (Python 3):
```#
# Author: Quickgrid ( Asif Ahmed )
# Site: https://quickgrid.wordpress.com
#

import sys
test_cases = open(sys.argv[1], 'r')
for test in test_cases:
print(test.lower())

test_cases.close()
```

## CodeEval Easy Level Challenge Odd Numbers

CodeEval Easy Level Challenge Odd Numbers:

##### Description:

For this problem there is no input. We just print odd numbers from 1 to 100. Here I have solved this problem in 4 programming languages c, c++, java, python. Have a look to learn the syntax difference between these.

There are many ways to solve this one. One way to solve can be starting at 1 and keep increment by 2 until we reach 99. Another can be checking if the number is divisible by 2.

##### C:
```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

#include <stdio.h>
int main(int argc, const char * argv[]) {
register unsigned int i = 1;
for(; i<=99; i+=2) printf("%u\n",i);
return 0;
}
```

##### C++:
```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

#include <iostream>
int main(int argc, const char * argv[]) {
register unsigned int i = 1;
for(; i<=99; ++i){
if(i&1) std::cout << i << "\n";
}
return 0;
}
```

##### Java:
```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

import java.io.*;
public class Main {
public static void main (String[] args) throws IOException {
for(int i=1; i<100; ++i){
if(i % 2 == 1) System.out.println(i);
}
}
}
```

##### Python (Python 3):
```#
# Author: Quickgrid ( Asif Ahmed )
# Site: https://quickgrid.wordpress.com
#

for i in range(1,100):
if(i%2):
print(i)

```

## UVA Problem 673 – Parentheses Balance Solution

UVA Problem 673 – Parentheses Balance Solution:

Solving Technique:

This problem can be solved easily using Stack ( also check out these problems i have solved using stack uva 11192uva 483 ).  Here the only corner case is space character. Input only contains three types of character 1st bracket, 3rd bracket and a space character.

Here i have provided three solutions. All have same logic. But first one is well commented and written for easier understanding. Second one is modified version of first. For the first and second code i take input as string but in the last i take input one by one as characters.

In the second code i have checked if length is odd then i know it can’t be balanced. So i just print NO. Which is “strlen(par) & 1“. It is equivalent to “strlen(par) % 2 == 1” meaning string length is odd.

The logic for this code is whenever we find a closing bracket it must have its corresponding opening bracket before ( to its immediate left ) that. So we remove those two and keep processing rest of the input. Example,

```[ [(  )]  ()]
```

Here we do nothing ( or, store them in string ) when we find an opening bracket. Whenever we find a closing bracket we see the character before that ( to its left ) is its opening bracket. If this condition doesn’t match then there is error in the input. So break immediately. Also when we find a closing bracket with its opening bracket we remove them and process rest of the input. Example,

```[ [(  )]  ()]  /* our input */
[ [] ()]       /* we remove first occurrence of closing and its corresponding opening bracket to its left */
[ ()]          /* Process rest of the input */
[ ]
/* Here nothing is left so it is a valid input */
```

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Critical Input:

###### More Critical inputs can be found in this link,

```3
([])
(([()])))
([ ()[  ]  ( )])()```

Output:

```Yes
No
Yes```

### Code Usage of Stack ( Explained ):

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 673 ( Parentheses Balance )
*/

#include<stdio.h>

/**
* Size for our stack although they said 128 but stack safety
*/
#define SIZE 256

/**
* Our stack or array to hold parenthesis
*/
static char stack[SIZE];
/**
* Our stack index counter
*/
int top = -1;

/**
* Push function of out stack, We basically store the character and increase the counter
* Checking of stack overflow is not implemented since stack size is large enough for this program
*/
void push(char c){
stack[++top] = c;
}

/**
* Set the element in current index to NUL and decrease the index
* Stack underflow never occurs for this program
*/
void pop(){
stack[top--] = '\0';
}

int main(){
register unsigned n, i;
unsigned char c;

/**
* Scan the test case count, getchar() is needed because i used gets() below which takes away my new line if getchar() is not used
*/
scanf("%u", &n); getchar();

while (n--){
stack[SIZE] = {'\0'};
/**
* Reset the stack index, meaning we start using our stack array from the beginning
*/
top = -1;
/**
* If no error then error is 0 else if there is error then error is 1
*/
unsigned error = 0;

/**
* Our character array to take the input string
*/
char *par = new char[SIZE + 1];
gets(par);

for (i = 0; par[i]; ++i){
/**
* Corner case the input can have space
*/
if(par[i] == ' ')
continue;

/**
* Push the character to stack if open bracket
*/
if(par[i] == '[' || par[i] == '(')
push(par[i]);

/**
* Pop or remove the element from top of stack if matching closing bracket found
*/
else if(par[i] == ']' && stack[top] == '[')
pop();
else if(par[i] == ')' && stack[top] == '(')
pop();

else{
/**
* If matching closing bracket not found then set error flag to 1 (ON)
*/
error = 1;
/**
* Since we found a mistake there is no need to process rest of the string
*/
break;
}
}

/**
* If error flag is on or there still exist some brackets on stack then print NO
*/
if(error || top > -1)
printf("No\n");
else
printf("Yes\n");
}
return 0;
}
```

### Taking input as string:(Faster)

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 673 ( Parentheses Balance )
*/

#include<stdio.h>
#include<string.h>

static char stack[256];
static char par[256];
int top;

int main(){
unsigned n, error;

scanf("%u", &n);
getchar();

while(n--){
gets(par);

if(strlen(par) & 1)
printf("No\n");
else{
stack[256] = {'\0'};
top = -1;
error = 0;

for(unsigned i = 0; par[i]; ++i){
if(par[i] == ' ')
continue;

if(par[i] == '[' || par[i] == '(')
stack[++top] = par[i];
else if((par[i] == ')' && stack[top] == '(') || (par[i] == ']' && stack[top] == '['))
--top;
else{
error = 1;
break;
}
}

(error || top > -1) ? printf("No\n") : printf("Yes\n");
}
}
return 0;
}
```

### Taking input one by one as characters:

```/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
* Problem: UVA 673 ( Parentheses Balance )
*/

#include<stdio.h>

#define SIZE 256

char stack[SIZE];

int main(){
register unsigned n, i;
unsigned ch;
scanf("%u", &n); getchar();

while(n--){
register int top = -1;
unsigned error = 0;

while ((ch = getchar()) != '\n'){
if (ch == ' ') continue;
if (ch == '[' || ch == '(') stack[++top] = ch;
else if ((ch == ']' && stack[top] == '[') || (ch == ')' && stack[top] == '(')) --top;
else error = 1;
}

if (error || top > -1) printf("No\n");
else printf("Yes\n");
}
return 0;
}
```