Count ways to N'th Stair(Order does not matter)
There are N stairs, and a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does not matter).
Note: Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same.
Input:
The first line contains an integer 'T' denoting the total number of test cases. In each test cases, an integer N will be given.
Output:
For each testcase, in a new line, print number of possible ways to reach Nth stair.
Constraints:
1 <= T <= 1000
1 <= N <= 106
Example:
Input:
2
4
5
Output:
3
3
Explanation:
Testcase 1: There are 3 ways to reach 4th stair.
Note: Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same.
The first line contains an integer 'T' denoting the total number of test cases. In each test cases, an integer N will be given.
For each testcase, in a new line, print number of possible ways to reach Nth stair.
1 <= T <= 1000
1 <= N <= 106
Input:
2
4
5
Output:
3
3
Testcase 1: There are 3 ways to reach 4th stair.
Solution-
class DynamicProgramming{
// function to find number of ways
Long countWays(int m){
// your code here
m=(m/2)+1;
Long l=Long.valueOf(m);
return l;
}
}
Question - Find the smallest positive number missing from an unsorted array
Input: {2, 3, 7, 6, 8, -1, -10, 15}Output: 1
Input: { 2, 3, -7, 6, 8, 1, -10, 15 }
Output: 4
Input: {1, 1, 0, -1, -2}
Output: 2
Solution-
import java.util.*;
class test
{
/* Utility function that puts all non-positive
(0 and negative) numbers on left side of
arr[] and return count of such numbers */
static int segregate (int arr[], int size)
{
int j = 0, i;
for(i = 0; i < size; i++)
{
if (arr[i] <= 0)
{
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
// increment count of non-positive
// integers
j++;
}
}
return j;
}
/* Find the smallest positive missing
number in an array that contains
all positive integers */
static int findMissingPositive(int arr[], int size)
{
int i;
// Mark arr[i] as visited by making
// arr[arr[i] - 1] negative. Note that
// 1 is subtracted because index start
// from 0 and positive numbers start from 1
for(i = 0; i < size; i++)
{
int x = Math.abs(arr[i]);
if(x - 1 < size && arr[x - 1] > 0)
arr[x - 1] = -arr[x - 1];
}
// Return the first index value at which
// is positive
for(i = 0; i < size; i++)
if (arr[i] > 0)
return i+1; // 1 is added becuase indexes
// start from 0
return size+1;
}
/* Find the smallest positive missing
number in an array that contains
both positive and negative integers */
static int findMissing(int arr[], int size)
{
// First separate positive and
// negative numbers
int shift = segregate (arr, size);
int arr2[] = new int[size-shift];
int j=0;
for(int i=shift;i<size;i++)
{
arr2[j] = arr[i];
j++;
}
// Shift the array and call
// findMissingPositive for
// positive part
return findMissingPositive(arr2, j);
}
// main function
public static void main (String[] args)
{
int arr[] = {0, 10,1,2, 2, -10, -20};
int arr_size = arr.length;
int missing = findMissing(arr, arr_size);
System.out.println("The smallest positive missing number is "+
missing);
}
}
Source-Geeksforgeeks
Question - Longest Common Substring in an Array of Strings
Input: grace graceful disgraceful gracefully
Output: grace
Input: sadness sad sadly
Output: sad
Output: grace
Input: sadness sad sadly
Output: sad
Solution -
// Java program to find the stem of given list of
// words
import java.io.*;
import java.util.*;
class stem {
// function to find the stem (longest common substring) from the string array
public static String findstem(String arr[])
{
// Determine size of the array
int n = arr.length;
// Take first word from array as reference
String s = arr[0];
int len = s.length();
String res = "";
for (int i = 0; i < len; i++) {
for (int j = i + 1; j <= len; j++) {
// generating all possible substrings
// of our reference string arr[0] i.e s
String stem = s.substring(i, j);
int k = 1;
for (k = 1; k < n; k++)
// Check if the generated stem is
// common to to all words
if (!arr[k].contains(stem))
break;
// If current substring is present in
// all strings and its length is greater
// than current result
if (k == n && res.length() < stem.length())
res = stem;
}
}
return res;
}
// Driver Code
public static void main(String args[])
{
String arr[] = { "grace", "graceful", "disgraceful", "gracefully" };
String stems = findstem(arr);
System.out.println(stems);
}
}
Question - Given an amount convert the amount into different currencies - example- amount to us,indian,france,china and display.
Solution-
import java.util.Scanner;
import java.text.NumberFormat;
import java.util.Locale;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
double payment = scanner.nextDouble();
scanner.close();
/* Create custom Locale for India.
I used the "IANA Language Subtag Registry" to find India's country code */
Locale indiaLocale = new Locale("en", "IN");
NumberFormat us = NumberFormat.getCurrencyInstance(Locale.US);
NumberFormat india = NumberFormat.getCurrencyInstance(indiaLocale);
NumberFormat china = NumberFormat.getCurrencyInstance(Locale.CHINA);
NumberFormat france = NumberFormat.getCurrencyInstance(Locale.FRANCE);
System.out.println("US: " + us.format(payment));
System.out.println("India: " + india.format(payment));
System.out.println("China: " + china.format(payment));
System.out.println("France: " + france.format(payment));
}
}
Question - Java Program to Print Diamond Pattern
Solution -
import java.util.*;
class dia
{
public static void main(String []args)
{
Scanner kb=new Scanner(System.in);
int n=kb.nextInt();
int i=0,j=0;
int space=n-1;
for (j = 1; j <= n; j++)
{
for (i = 1; i <= space; i++)
{
System.out.print(" ");
}
space--;
for (i = 1; i <= 2 * j - 1; i++)
{
System.out.print("*");
}
System.out.println("");
}
space = 1;
for (j = 1; j <= n - 1; j++)
{
for (i = 1; i <= space; i++)
{
System.out.print(" ");
}
space++;
for (i = 1; i <= 2 * (n - j) - 1; i++)
{
System.out.print("*");
}
System.out.println("");
}
}
}
Question - Write a program to evaluate the postfix expression
input = a mathematical expression
example = 231*+9-
output = -4
Solution
import java.util.Stack;
class main
{
static int evaluatePostfix(String exp)
{
Stack<Integer> stack=new Stack<>();
for(int i=0;i<exp.length();i++)
{
char c=exp.charAt(i);
if(Character.isDigit(c))
stack.push(c - '0');
else
{
int val1 = stack.pop();
int val2 = stack.pop();
switch(c)
{
case '+':
stack.push(val2+val1);
break;
case '-':
stack.push(val2- val1);
break;
case '/':
stack.push(val2/val1);
break;
case '*':
stack.push(val2*val1);
break;
}
}
}
return stack.pop();
}
public static void main(String[] args)
{
String exp="231*+9-";
System.out.println("postfix evaluation: "+ evaluatePostfix(exp));
}
}
Question - Given a collection of intervals, merge all the overlapping intervals, for example-
given - [1,3] [2,6] [8,10] [15,18]
output- [1,6] [8,10] [15,18]
Solution-
import java.util.*;
class main
{
public static void main(String []args)
{
Scanner kb=new Scanner(System.in);
int n=kb.nextInt();
int arr1[]=new int[n];
int arr2[]=new int[n];
int arr3[]=new int[n];
int arr4[]=new int[n];
int i,j,k=0;
int temp1=0,temp2=0;
for(i=0;i<n;i++)
{
arr1[i]=kb.nextInt();
arr2[i]=kb.nextInt();
}
for(j=0;j<n-1;j++)
{
if(arr2[j]>arr1[j+1])
{
System.out.println("Found at "+ arr1[j+1] +" and "+ arr2[j]);
temp1=j;
temp2=j+1;
}
}
}
}
Question - Given an array of N elements, determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is same.
input format- Input to contain a number of elements N, next line contain the N elements
5
3 1 5 9 12
Output format- Can be divided into two subsets of an equal sum
Solution-
import java.io.*;
class main
{
static boolean isSubsetSum (int arr[], int n, int sum)
{
if (sum == 0)
return true;
if (n == 0 && sum != 0)
return false;
if (arr[n-1] > sum)
return isSubsetSum (arr, n-1, sum);
return isSubsetSum (arr, n-1, sum) ||
isSubsetSum (arr, n-1, sum-arr[n-1]);
}
static boolean findPartition (int arr[], int n)
{
int sum = 0;
for (int i = 0; i < n; i++)
sum += arr[i];
if (sum%2 != 0)
return false;
return isSubsetSum (arr, n, sum/2);
}
public static void main (String[] args)
{
int arr[] = {3, 1, 5, 9, 12};
int n = arr.length;
if (findPartition(arr, n) == true)
System.out.println("Can be divided into two "+
"subsets of equal sum");
else
System.out.println("Can not be divided into " +
"two subsets of equal sum");
}
}
__________________________________________________
source- geeksforgeeks.com
Question - You Are given an alphanumeric String. Write a program to find the sum of numbers in the given string.
input format-51b6de19
output format -21
Solution
import java.util.Scanner;
class main
{
public static void main(String [] args)
{
Scanner kb=new Scanner(System.in);
String word=kb.nextLine();
int length=word.length();
int sum=0;
for(int i=0;i<length;i++)
{
if(Character.isDigit(word.charAt(i)))
{
int temp=Character.getNumericValue(word.charAt(i));
sum=sum+temp;
}
}
System.out.println("The sum is" +sum);
}
}
