Skip to content

Instantly share code, notes, and snippets.

@nichtemna
nichtemna / Fibonacci.java
Created August 10, 2016 16:10
Fibonacci number by table method
import java.util.Scanner;
public class Fib {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int n = scaner.nextInt();
if (n <= 80) {
System.out.println("Fibonacci number for " + n + " = " + getFibonacci(n));
} else {
System.out.println("To big input");
@nichtemna
nichtemna / Fibonacci.java
Created August 10, 2016 16:11
Last Digit of a Large Fibonacci Number
*/
public class FibLast {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int n = scaner.nextInt();
System.out.println("Last digit for " + n + " = " + getFibonacci(n));
}
private static int getFibonacci(int n) {
int[] fib = new int[n+1];
@nichtemna
nichtemna / GCD.java
Created August 10, 2016 16:20
Greatest common divisor for two numbers
import java.util.Scanner;
/**
* Created by root on 10.08.16.
*/
public class GCD {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int first = scaner.nextInt();
int second = scaner.nextInt();
@nichtemna
nichtemna / LCM.java
Created August 11, 2016 09:04
Least common multiple of two numbers
public class LCM {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int first = scaner.nextInt();
int second = scaner.nextInt();
int gcd = getGCD(first, second);
long lcm = getLCM(first, second, gcd);
System.out.println(lcm);
}
@nichtemna
nichtemna / LCM.java
Created August 11, 2016 09:04
Least common multiple of two numbers
public class LCM {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int first = scaner.nextInt();
int second = scaner.nextInt();
int gcd = getGCD(first, second);
long lcm = getLCM(first, second, gcd);
System.out.println(lcm);
}
@nichtemna
nichtemna / GreedyCoins.java
Created August 11, 2016 14:08
Minimum number of coins needed to change the input value into coins with denominations 1, 5, and 10.
import java.util.Scanner;
/**
* Created by root on 11.08.16.
*/
public class GreedyCoins {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int m = scaner.nextInt();
if (m < 1 || m > Math.pow(10, 3)) {
@nichtemna
nichtemna / GreedyCoins.java
Created August 11, 2016 14:08
Minimum number of coins needed to change the input value into coins with denominations 1, 5, and 10.
import java.util.Scanner;
/**
* Created by root on 11.08.16.
*/
public class GreedyCoins {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
int m = scaner.nextInt();
if (m < 1 || m > Math.pow(10, 3)) {
@nichtemna
nichtemna / Combinations.java
Last active August 15, 2016 11:44
Get all possible combinations of symbols - Recursion
public class Combinations {
public static void main(String[] args) {
List<String> data = new ArrayList<>();
data.add("a");
data.add("b");
data.add("c");
data.add("d");
List<String> result = getCombinations(data);
for (String string : result) {
@nichtemna
nichtemna / Loot.java
Created August 15, 2016 12:27
Knapsack problem
A thief finds much more loot than his bag can fit.
Help him to find the most valuable combination of items assuming that
any fraction of a loot item can be put into his bag.
Task. The goal of this code problem is to implement an algorithm for the fractional knapsack problem.
Input Format. The first line of the input contains the number n of items and the capacity W of a knapsack.
The next n lines define the values and weights of the items. The i-th line contain integers v and w —
the value and the weight of i-th item, respectively.
Constraints. 1 ≤ n ≤ 10^3
0 ≤ W ≤ 2 · 10^6
@nichtemna
nichtemna / SmallestCommon.java
Created August 29, 2016 14:59
Find the smallest common element in two arrays
import java.util.*;
/**
* Find the smallest common element in two arrays , if no return -1. Algorithm works in a linear time
*/
public class SmallestCommon {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();