Simple Array Sum

You are given an array of integers of size N. Can you find the sum of the elements in the array?

Input
The first line of input consists of an integer N. The next line contains N space-separated integers representing the array elements.
Sample:

6

1 2 3 4 10 11

Output
Output a single value equal to the sum of the elements in the array.
For the sample above you would just print 31 since 1+2+3+4+10+11=31.

```import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int sum = 0;
for(int i=0;i
```

Candies

Alice is a kindergarden teacher. She wants to give some candies to the children in her class. All the children sit in a line ( their positions are fixed), and each of them has a rating score according to his or her performance in the class. Alice wants to give at least 1 candy to each child. If two children sit next to each other, then the one with the higher rating must get more candies. Alice wants to save money, so she needs to minimize the total number of candies given to the children.

Input Format

The first line of the input is an integer N, the number of children in Alice’s class. Each of the following N lines contains an integer that indicates the rating of each child.

Output Format

Output a single line containing the minimum number of candies Alice must buy.

Sample Input

3
1
2
2
Sample Output

4
Explanation

Here 1, 2, 2 is the rating. Note that when two children have equal rating, they are allowed to have different number of candies. Hence optimal distribution will be 1, 2, 1

```
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
int []r = new int[n];
for(int i=0; iscore[i]) c[i+1]=c[i]+1;
}
for(int i=n-1; i>0; i--){
if(score[i-1]>score[i]&&!(c[i-1]>c[i])) c[i-1]=c[i]+1;
}

for(int i:c) sum+=i;

return sum+n;

}
}

```

Find whether number is prime or not

```
import java.util.Scanner;

public class IsPrime {
public static void main(String args[]){
System.out.println("Enter a number");
Scanner sc = new Scanner(System.in);
int number=sc.nextInt();
if(isPrime(number)){
System.out.println("Number is Prime");
}else{
System.out.println("Number is not Prime");
}
}

private static boolean isPrime(int number) {
if(number<2)return false;
for(int i=2;i<=Math.sqrt(number);i++){
if(number%i==0) return false;
}
return true;
}
}

```

Coding Puzzle : Tree Design

Problem:

Write a program that prints a tree made out of ‘*’  and ‘|’ . Shape of the tree depends on the given number N.

Input Format:

Given an integer N.

Output Format:

Display the corresponding tree to standard output.

Constraints: 1 <= N <= 60

Sample Input

1

Sample Output

```   *
***
*****
*******
|
```

Sample Input

2

Sample Ouput

```      *
***
*****
*******
*****
*******
*********
***********
*************
|||
|||
```

Please consult them to confirm patterns and spacings in the output.

Solution Code:

```import java.util.Scanner;

public class TreeDesign {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int N = sc.nextInt();
int height =0;
int[] rows = new int[N];
for (int i = 0; i < N; i++) {
rows[i] = 4 + i;
height+=rows[i];
}

int width = 7;
for (int i = 1; i < N; i++) {
if (i % 2 == 0) {
width = width + (rows[i] - 1) * 2 - 4;
} else {
width = width + (rows[i] - 1) * 2 - 2;
}
}
char [][] tree = new char[height + N][width];
for (int q = 0; q < height+N; q++) {
for (int p = 0; p < width; p++) {
tree[q][p]=' ';
}
}

int z=0;
int x = 0;
for (int t = N - 1; t >= 0; t--) {

for (int i = height - 1-z; i >= height -z- rows[t] ; i--) {

for (int j = x; j < width - x; j++) {
tree[i][j] = '*';
}
x++;
}
if (t % 2 == 0) {
x = x - 1 - 1-1;
} else {
x = x - 1 - 1 ;
}
z=z+rows[t];
}

int middle = width/2;
int index = middle -N/2;
for (int q = height; q < height+N; q++) {
for (int p = index; p <= middle+N/2; p++) {
tree[q][p]='|';
}
}
for (int q = 0; q < height+N; q++) {
System.out.println(new String(tree[q]));
}
}
}
```

Problem :

A positive integer is called an additive prime number if it is prime and the sum of its digits is also prime.

For example, 83 is prime, and 8 + 3 = 11, which is also prime. Thus, 83 is an additive prime. Note that all single digit primes sum to themselves, and are thus additive primes.

Input Format:

Given an integer N.

Output Format:

Sample Input00:

1

Sample Output00:

2

Sample Input01:

2

Sample Output01:

3

Sample Input02:

9

Sample Output02:

43

Constraints:

1 <= N <= 200,000

Solution Code:

```import java.util.Scanner;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int N = Integer.parseInt(sc.nextLine());
int S =N*50;
boolean[] isPrime = new boolean[S];

int l = 0;
int number = 2;

for(int i=2;i

```

Coding Puzzle: Recycled Numbers

(Puzzle from Google Codejam Qualifier Round 2012)

Problem

Do you ever become frustrated with television because you keep seeing the same things, recycled over and over again? Well I personally don’t care about television, but I do sometimes feel that way about numbers.

Let’s say a pair of distinct positive integers (n, m) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order. For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.

Given integers A and B with the same number of digits and no leading zeros, how many distinct recycled pairs (n, m) are there with An < mB?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of a single line containing the integers A and B.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1), and y is the number of recycled pairs (n, m) with An < mB.

Limits

1 ≤ T ≤ 50.
A and B have the same number of digits.

1 ≤ AB ≤ 1000.

Large dataset

1 ≤ AB ≤ 2000000.

Sample

 Input Output ``` 4 1 9 10 40 100 500 1111 2222 ``` ``` Case #1: 0 Case #2: 3 Case #3: 156 Case #4: 287 ```

Solution:
-Rotate a number (mathematically)
-If number lies between A & B increment total
-Print total/2 (All pairs occur twice)

```import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;

public class RecycledNumbers {
public static void main(String args[]) throws IOException {

Writer output = null;
File file = new File("outputC.txt");
output = new BufferedWriter(new FileWriter(file));

int i = 0;
while (i < T) {

int total = 0;
int A = Integer.parseInt(temp[0]);
int B = Integer.parseInt(temp[1]);
for (int j = A; j <= B; j++) {

long number = j;
long start = number;

int numdigits = (int) Math.log10((double) number);
int multiplier = (int) Math.pow(10.0, (double) numdigits);

while (true)
{
long r = number % 10;
number = number / 10;
number = number + multiplier * r;

if (number == start)
break;
if ((int) number >= A && (int) number <= B) {
total++;
}
}
}

output.write("Case #" + (i + 1) + ": " + (total / 2));
if (i != T - 1) {
output.write("\n");
}

i++;
}
output.close();
}
}

```

Test Files (Large Dataset)
Input->Input.txt
Output-> Output.txt

Coding Puzzle : Punch

Puzzle:

We have n punching bags in a row. Mr Lee is going to practice with them for the upcoming Boxing tournament.

Each bag has a resistance level. Mr Lee can punch a bag if its resistance is greater than 0. He is an extremely hard puncher: when Mr Lee punches a bag, not only is its resistance set to 0 (ie: the bag is destroyed), but also the resistances of its immediately adjacent neighbors( one on left and other on right ) are decreased by one. If at any point of time the resistance of a bag drops to zero or less it is considered as destroyed. A punch on a bag with resistance greater than 0 has no impact on an immediate neighbor which is already destroyed.

Mr Lee wants to maximize his (very expensive) workout sessions, and would like to punch on these bags as much as possible. For any set of punching bags, what is the maximum number of punches that he can perform?

Input Format

On the only line of input there are n characters describing the resistances of the bags from 1 to n.

Ouput Format

On the only line of the output print an integer describing the maximum number of punches Mr Lee can punch for that set of bags.

Sample Input

11

Sample Ouput

1

Sample Input

021

Sample Output

2

Explanation

In the first example there are two bags, and we can punch only one of them before destroying both. In the second example we can punch on the third bag and then on the second bag to obtain two punches.

Constraints

Each bag has a resistance level between 0 and 3 ( inclusive ) and the number of bags is not more than 100

Solution:

-Find bag with minimum resistance
-Punch that bag and decrement the neighbors

Code:

```import java.util.Scanner;

public class Punch {
static int []A;
static int total;
public static void main (String args[]) {
Scanner sc = new Scanner(System.in);
String input  = sc.next();

int numdigits = input.length();
A = new int[numdigits];

for(int i=0;i
```

Counting Comparisons in QuickSort [Java]

Compute the total number of comparisons used to sort the given input file by QuickSort.

(Programming Question from coursera.org)

The file contains all of the integers between 1 and 10,000 (inclusive) in unsorted order (with no integer repeated). The integer in the ith row of the file gives you the ith entry of an input array.

Your task is to compute the total number of comparisons used to sort the given input file by QuickSort. As you know, the number of comparisons depends on which elements are chosen as pivots, so we’ll ask you to explore three different pivoting rules.
You should not count comparisons one-by-one. Rather, when there is a recursive call on a subarray of length m, you should simply add m−1 to your running total of comparisons. (This is because the pivot element will be compared to each of the other m−1 elements in the subarray in this recursive call.)

WARNING: The Partition subroutine can be implemented in several different ways, and different implementations can give you differing numbers of comparisons. For this problem, you should implement the Partition subroutine as it is described in the video lectures (otherwise you might get the wrong answer).

DIRECTIONS FOR THIS PROBLEM:

For the first part of the programming assignment, you should always use the first element of the array as the pivot element.

Code:-

```
import java.io.IOException;

public class Comparisons {

static long noOfComparisons;
public static void main(String args[]) throws IOException {

int n =10000;
int[] A = new int[n];
int i = 0;
while (str != null) {
A[i] = Integer.parseInt(str);
i++;
}

QuickSort(A,0,A.length-1);

System.out.println(noOfComparisons);

}

private static void QuickSort(int[] a, int l, int r) {

int pivot;
if(r>l){
pivot =Partition(a,l,r);

QuickSort(a, l, pivot-1);
QuickSort(a, pivot+1, r);
}
}

private static void add(int i) {
noOfComparisons+=i;

}

private static int Partition(int[] a, int l, int r) {

int p=a[l];
int i =l+1;

for(int j=l+1;j<=r;j++){
if(a[j]
Output: 162085
Problem2:
Use Last element as pivot .
Solve this problem using same Partition function by swapping first and last element and then using same first element as pivot.
.......
.......

private static int Partition(int[] a, int l, int r) {

Swap(a,l,r);

int p=a[l];
int i =l+1;
.......
.......

Output: 164123
```

Counting Inversions in Java

Given array A[1… n], for every i < j, find all inversion pairs such that A[i] > A[j]
(i, j form an inversion if A[i] > A[j])

Example
2 4 1 3 5
The sequence 2, 4, 1, 3, 5 has three inversions (2,1), (4,1), (4,3).

Problem

Find the number of inversions in the file given (every row has a single integer between 1 and 100,000) . Assume your array is from 1 to 100,000 and ith row of the file gives you the ith entry of the array.

Code– O(n log n)

```import java.io.BufferedReader;
import java.io.IOException;

public class Inversions {
public static void main(String args[]) throws IOException {

int n = 100000;
int[] A = new int[n];
int i = 0;
while (str != null) {
A[i] = Integer.parseInt(str);
i++;
}

Pair a = sortAndCount(A);
System.out.println(a.x);
}

private static Pair sortAndCount(int[] a) {
if (a.length == 1) {
return new Pair(a, 0);
} else {
int[] leftArray = new int[a.length / 2];
System.arraycopy(a, 0, leftArray, 0, leftArray.length);
int[] rightArray = new int[a.length - leftArray.length];
System.arraycopy(a, leftArray.length, rightArray, 0,
rightArray.length);
Pair x = sortAndCount(leftArray);

Pair y = sortAndCount(rightArray);
Pair z = MergeAndCountSplitInv(x.Array, y.Array, a.length);

return new Pair(z.Array, x.x + y.x + z.x);
}

}

private static Pair MergeAndCountSplitInv(int[] B, int[] C, int n) {
long total = 0;
int[] D = new int[n];
int i = 0;
int j = 0;
for (int k = 0; k < n; k++) {
if (j == C.length || i != B.length && B[i] < C[j]) {
D[k] = B[i];
i++;
} else if (i == B.length || j != C.length && C[j] < B[i]) {
D[k] = C[j];
j++;
total += B.length - i;
}
}
return new Pair(D, total);
}
}

class Pair {
Pair(int[] A, long l) {
this.Array = A;
this.x = l;
}

public int[] Array;
public long x;
}

```

Output : 2407905288

Validating file path in Java

Import File class

`import java.io.File;`

Create a new File Instance by giving full pathname String of file/folder

`File file = new File("Full-path-to-file-or-folder");`

• Checking if File/Folder exists
```		if (file.exists()) {
// File Exists
} else {
// File does not exist
}```
• Check if path specified is a Directory
```		if (file.isDirectory()) {
// Directory
}```
• Check if application can read/write to file/folder at specified path
```		if (file.canRead()) {
}
if (file.canWrite()) {
// Application can write File /Folder
}
if (file.canExecute()) {
// Application can execute file
}```

There may be problems in using canWrite() method in Windows and may not give correct results. Here is a workaround-

Define a method which takes file as input.

Use file.createNewFile() and file.delete() in try block and return true.

If these methods fail then return false in catch block

```public boolean checkWritable(File file) {
try {
file.createNewFile();
file.delete();
return true;
} catch (Exception e) {
return false;
}
}```

You can also try opening the file with FileOutputStream and then catch the exceptions.