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

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;

     }*/

}