Friday 28 November 2014

Next Greater Element

Next Greater Element
Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.
Examples:
a) For any array, rightmost element always has next greater element as -1.
b) For an array which is sorted in decreasing order, all elements have next greater element as -1.
c) For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.
Element       NGE
   4      -->   5
   5      -->   25
   2      -->   25
   25     -->   -1
d) For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows.
  Element        NGE
   13      -->    -1
   7       -->     12
   6       -->     12
   12     -->     -1



Java Solution using Stacks :


package nextGreaterElement;
import java.util.Stack;
public class NGE // next greater element
{
 public static void main(String[] args) 
 {
  int A[]={7,8,9,4,5,6,1,2,3};
  Stack<Integer> S=new Stack<Integer>();
  S.push(new Integer(A[0]));
  for(int i=1;i<A.length;i++)
  {
   int current=A[i];
   while(true)
   {
    if(S.isEmpty())
    {
     S.push(new Integer(current));
     break;
    }
    int element=S.pop().intValue();
    if(element>current)
    {
     S.push(new Integer(element));
     S.push(new Integer(current));
     break;
    }
    System.out.println(element+" -> "+current);
   }
  }
  while(!S.isEmpty())
   System.out.println(S.pop()+" -> "+"-1");
 }
}


Time Complexity : O(n)
Note that when you use two loops to iterate through the array to find the next greater element your time complexity will be O(n*n), but by using the above mentioned method of stacks, we can reduce the time complexity to O(n).

Thursday 27 November 2014

CODECHEF - PRIME1

Your task is to generate all prime numbers between two given numbers.

Input

The first line contains t, the number of test cases (less then or equal to 10).
Followed by t lines which contain two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n,
one number per line. Separate the answers for each test case by an empty line.

Example

Input:
2
1 10
3 5

Output:
2
3
5
7

3
5


JAVA SOLUTION

package primes1;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main 
{
 //partitioned Seive of Eratosthenes
  
 public static void main(String[]args)throws IOException
 {
  int max=(int)Math.sqrt(1000000001)+1;
  boolean primes[]=new boolean[max+1];
  //primes[0] and primes[1] should be false by default 
  //because they 0 and 1 are not primes.

  for(int i=2;i<=max;i++)
   primes[i]=true;
  for(int i=2;i*i<=max;i++)
   if(primes[i])
    for(int j=i*i;j<=max;j+=i)
     primes[j]=false;
  
  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  int t=Integer.parseInt(br.readLine());
  while(t-->0)
  {
   StringTokenizer stz=new StringTokenizer(br.readLine());
   int m=Integer.parseInt(stz.nextToken());
   int n=Integer.parseInt(stz.nextToken());
   boolean newPrimes[]=new boolean[n-m+1];
   for(int i=0;i<newPrimes.length;i++)
    newPrimes[i]=true;
   for(int i=2;i<=Math.sqrt(n);i++)
    if(primes[i]) // means i is a prime number.
     for(int j=(m/i)*i;j<=n;j+=i)
     {
      if(j-m < 0)
       continue;
      newPrimes[j-m]=false;
     }
   
   for(int i=0;i<=Math.sqrt(n);i++)
    if(i>=m && i<=n && primes[i])
     System.out.println(i);
    
   for(int i=0;i<newPrimes.length;i++)
    if(newPrimes[i] && i+m!=1)
     System.out.println(""+(i+m));
   System.out.println();
  }
 }
}

Friday 21 November 2014

SEIVE OF ERATOSTHENES

SEIVE OF ERATOSTHENES

Suppose, we need to find all the prime numbers upto a very large number N. We first make a boolean array primes[N] and initialize each element to say ‘true’. Now we run an outer for loop from i=2(the first prime number) to i<=sqrt(N) and in each loop we check that for the value of primes[i], if it is true then we run another nested loop from j=i^2 till j<=N and increment the loop-counter of inner nested loop by i; and within this inner loop set primes[j] = false.
When the algorithm terminates, all the numbers in the ‘primes’ array that are ‘true’ are prime.

ALGORITHM:
Input: an integer n > 1

Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

 for i = 2, 3, 4, ..., not exceeding n:
  if A[i] is true:
    for j = i2, i2+i, i2+2i, ..., not exceeding n:
      A[j] := false

Output: all i such that A[i] is true are prime.

Implementation in Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
     public static void main(String[]args)throws IOException
     {
          BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
          System.out.print("Enter N : ");
          int n=Integer.parseInt(br.readLine());
          boolean primes[]=new boolean[n+1];
          /* primes[0] and primes[1] should be false by default
           * because they 0 and 1 are not primes.
           */
          for(int i=2;i<=n;i++)
              primes[i]=true;
          for(int i=2;i*i<=n;i++)
              if(primes[i])
                   for(int j=i*i;j<=n;j+=i)
                        primes[j]=false;
          for(int i=0;i<=n;i++)
              if(primes[i])
                   System.out.println(i);
     }
}


Sunday 2 November 2014

PROJECT EULER SOLUTION # 82

PROJECT EULER PROBLEM # 82
NOTE: This problem is a more challenging version of Problem 81.
The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.
131
673
234
103
18
201
96
342
965
150
630
803
746
422
111
537
699
497
121
956
805
732
524
37
331
Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the left column to the right column.


PROJECT EULER SOLUTION # 82

#include<stdio.h>
int mat[80][80],minimum[80][80],n;
int min2(int a,int b)
{
    return (a>b?b:a);
}
int min3(int a,int b,int c)
{
    return (a<b?(min2(a,c)):(min2(b,c)));
}

int main()
{
    int min,i,j;
    char temp;
    FILE *f;
    n=9;
    f=fopen("matrix.txt","r");
    if(f)
    {
        for(i=0;i<n;i++)
        {
            for(j=0;j<n-1;j++)
                fscanf(f," %d%c",&mat[i][j],&temp);
            fscanf(f,"%d",&mat[i][j]);
        }

        for(i=0;i<n;i++)
            minimum[i][0]=mat[i][0];
        for(i=1;i<n;i++)
        {
            j=0;
            minimum[j][i]=mat[j][i]+min2(minimum[j][i-1],minimum[j+1][i-1]+mat[j+1][i]);
            for(j=1;j<n;j++)
                minimum[j][i]=mat[j][i]+min2(minimum[j][i-1],minimum[j-1][i]);

            for(j=n-2;j>=0;j--)
                minimum[j][i]=min2(minimum[j+1][i]+mat[j][i],minimum[j][i]);
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
                printf("%d ",minimum[i][j]);
            printf("\n");
        }
        min=2147483647;
        for(i=0;i<n;i++)
            if(min>minimum[i][n-1])
                min=minimum[i][n-1];
        printf("answer = %d\n",min);
    }
    else
        printf("there is some error in opening the file\n");
    return 0;
}


PROJECT EULER SOLUTION # 59

PROJECT EULER PROBLEM # 59
Each character on a computer is assigned a unique code and the preferred standard is ASCII (American Standard Code for Information Interchange). For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.
A modern encryption method is to take a text file, convert the bytes to ASCII, then XOR each byte with a given value, taken from a secret key. The advantage with the XOR function is that using the same encryption key on the cipher text, restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.
For unbreakable encryption, the key is the same length as the plain text message, and the key is made up of random bytes. The user would keep the encrypted message and the encryption key in different locations, and without both "halves", it is impossible to decrypt the message.
Unfortunately, this method is impractical for most users, so the modified method is to use a password as a key. If the password is shorter than the message, which is likely, the key is repeated cyclically throughout the message. The balance for this method is using a sufficiently long password key for security, but short enough to be memorable.
Your task has been made easy, as the encryption key consists of three lower case characters. Using cipher1.txt (right click and 'Save Link/Target As...'), a file containing the encrypted ASCII codes, and the knowledge that the plain text must contain common English words, decrypt the message and find the sum of the ASCII values in the original text.


PROJECT EULER SOLUTION # 59
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
char keyArray[3],answerArray[3];
int maxSpaces=0;
int isAValidEnglishCharacter(char temp)
{
    if(temp<32 || temp>126)
        return 0;
    return 1;
}

int isKeyPossible(char a,char b,char c,char*arr,int n)
{
    int i,flag,spaces;
    keyArray[0]=a;
    keyArray[1]=b;
    keyArray[2]=c;

    flag=0;
    spaces=0;
    for(i=0;i<n;i++)
    {
        if(((char)keyArray[i%3]^(char)arr[i])==' ')
            spaces++;
        if(!isAValidEnglishCharacter((char)keyArray[i%3]^(char)arr[i]))
            return 0;
    }
    if(maxSpaces<spaces) // as the most common english character is space (' ')
    {
        maxSpaces=spaces;
        answerArray[0]=a;
        answerArray[1]=b;
        answerArray[2]=c;
    }
    return 1;
}

void findKey(char*arr,int n)
{
    char i,j,k;
    int l,answer[3];
    /*
        the encryption key consists of three lower case characters
    */
    for(i='a';i<='z';i++)
        for(j='a';j<='z';j++)
            for(k='a';k<='z';k++)
                if(isKeyPossible(i,j,k,arr,n))
                    printf("Key found key is %c%c%c\n",i,j,k);
}
int main()
{
    char temp;
    int answer;
    int arr[5000],numberOfElements;
    char byteArray[5000];
    int i,key;
    FILE*fptr;
    fptr=fopen("cypher1.txt","r");
    if(fptr)
    {
        for(i=0;!feof(fptr);i++)
        {
            fscanf(fptr,"%d",&arr[i]);
            byteArray[i]=(char)arr[i];
            fscanf(fptr," %c",&temp);
        }
        numberOfElements=i;
        /* eliminating the duplicates from the array */
        findKey(byteArray,numberOfElements);
        /*
        for(i=0;i<numberOfElements;i++)
            printf("%c",(key^arr[i]));
        */
        answer=0;
        /*
        keyArray[0]='g';
        keyArray[1]='o';
        keyArray[2]='d';
        */
        for(i=0;i<numberOfElements;i++)
        {
            printf("%c",(byteArray[i]^answerArray[i%3]));
            answer+=(byteArray[i]^answerArray[i%3]);
        }
        printf("\nanswer = %d\n",answer);
    }
    else
        printf("There was some problem in opening the file\n");
    return 0;
}