Wednesday, August 31, 2016

Finding a Majority Element

Problem Description Task.
The goal in this code problem is to check whether an input sequence contains a majority element.
Input Format. The first line contains an integer 𝑛, the next one contains a sequence of 𝑛 non-negative integers 𝑎0, 𝑎1, . . . , 𝑎𝑛−1. Constraints. 1 ≤ 𝑛 ≤ 10^5 ; 0 ≤ 𝑎𝑖 ≤ 10^9 for all 0 ≤ 𝑖 < 𝑛.
Output Format. Output 1 if the sequence contains an element that appears strictly more than 𝑛/2 times, and 0 otherwise.
Pseudo code
findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++
    (b) Else
        count--;
    (c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

Java Code
import java.util.Scanner;

// Moore- Voting algorithm . Run-time complexity O(n)
public class MajorityElement {
     public static void main(String[] args) {
           Scanner scan = new Scanner(System.in);
           int n = scan.nextInt();
           long array[] = new long[n];
           for (int i = 0; i < n; i++)
                array[i] = scan.nextLong();
           long candidate = findCandidate(array, n);
           System.out.println(candidate);
           int count = 0;
           for (int i = 0; i < n; i++)
                if (array[i] == candidate)
                     count++;
           if (count > (n / 2))
                System.out.println("1");
           else
                System.out.println("0");
     }

     static long findCandidate(long array[], int n) {
           int index = 0;
           long count = 1;
           for (int i = 1; i < n; i++) {
                if (array[index] == array[i])
                     count++;
                else
                     count--;
                if (count == 0)
                     {index = i;
                      count = 1;}
           }
           return array[index];
     }
}

Output:
10
2 124554847 2 941795895 2 2 2 2 792755190 756617003

2

1

Tuesday, August 30, 2016

Fractional Knapsack

Algorithm- Fractional Knapsack

import java.util.Scanner;

public class Knapsack01 {
     public static void main(String[] args) {
           Scanner scan = new Scanner(System.in);
           int n = scan.nextInt(); // 1
           int W = scan.nextInt(); // 1000
           float value[] = new float[n]; // 500
           float weight[] = new float[n]; // 30
           float ratio[] = new float[n];
           for (int i = 0; i < n; i++) {
                value[i] = scan.nextInt();
                weight[i] = scan.nextInt();
                ratio[i] = value[i] / weight[i];
           }
           float totalValue = knapSack01(W, value, weight, ratio, n);
           System.out.println(totalValue);
     }

     public static float knapSack01(float W, float[] value, float weight[], float ratio[],
                int n) {
           float V = 0;
           while (n>0 && W!=0) {
                int mI = maxIndex(n, ratio);
                float w=min(weight[mI],W);
                // W=40,weight[2]=30 // W=10,weight[0]=20;
                W = W - w;
                V = V + w*ratio[mI];
                weight[mI]=weight[mI]-w;
                ratio[mI] = 0;
                n--;
           }
           return V;
     }
     public static float min(float a,float b){
           return a>b?b:a;
     }

     public static int maxIndex(int n, float ratio[]) {
           float largest = Integer.MIN_VALUE;
           int lastIndex = 0;
           for (int i = 0; i < n; i++) {
                if (ratio[i] > largest) {
                     largest = ratio[i];
                     lastIndex = i;
                }
           }
           return lastIndex;
     }
}

Output:
Input: 3 50
60 20 100
50 120 30

Output: 180.0000

Simple Algorithms- Fibonacci,finding GCD & finding LCM

Algorithm 1- Finding Fibonacci number with better time complexity

import java.util.Scanner;

//0,1,1,2,3,5,8,13,21,34...
//fun(n)=fun(n-1)+fun(n-2) where n>=2
/*fib(9)=fib(8)+fib(7)
=fib(7)+fib(6)+fib(6)+fib(5)
=fib(6)+fib(5)+fib(5)+fib(4)+fib(5)+fib(4)+fib(4)+fib(3)
*/
public class FibonacciNumberFast {
     public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);
           int n = scanner.nextInt();
           long fno=fibonacciNumber(n);
           System.out.println(fno);  
     }
     public  static long fibonacciNumber(int n){
           int array[]= new int[n+1];
           array[0]=0;
           if(n==0)
                return array[0];
           array[1]=1;
           for(int i=2;i<=n;i++)
                array[i]=array[i-1]+array[i-2];
           return array[n];
     }
}

Algorithm 2– Finding GCD of a number
 1) GCD using Recursion
                          2) GCD using naïve approach

import java.util.Scanner;

// Largest number which divides both a and b
public class GCDNaive {
     public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);
           long a = scanner.nextLong();
           long b = scanner.nextLong();
           //long gcd = gcd(a, b);
           //System.out.println("Result from GCD Naive "+gcd);
           gcdFast(a, b);
     }
     static void gcdFast(long a, long b) {
           if (b == 0) {
                System.out.println(a);
           System.exit(0);
           }
           long rem=a%b;
           gcdFast(b, rem);
     }
/*   static long gcd(long a, long b) {
           long best = 0;
           for (long i = 1; i <= a + b; i++) {
                if ((a%i ==0) && (b%i== 0))
                     best = i;
           }
           return best;
     }
*/}

Algorithm 3– Finding LCM of a number

import java.util.Scanner;

// GCD(a,b)*LCM(a,b)=a*b
public class LCM {
     public static void main(String[] args) {
           Scanner scanner = new Scanner(System.in);
           long a = scanner.nextLong(); // 8
           long b = scanner.nextLong(); // 6
           // long c = gcd(a, b);
           // System.out.println("GCD is" + c);
           long c = gcdFast(a, b);
           long d = (a * b) / c;
           System.out.println(d);
     }

     static long gcdFast(long a, long b) {
           if (b == 0) {
                return a;
           }
           long rem = a % b;
           long c=gcdFast(b, rem);
           return c;
     }

     /*   static long gcd(long a, long b) {
           long best = 0;
           for (long i = 1; i <= a + b; i++) {
                if ((a % i == 0) && (b % i == 0))
                     best = i;
           }
           return best;
     }*/
}