Thursday, 29 July 2021

Pascal's Triangle - LeetCode 118

 Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Solution: 

Note: Only function is written


class Solution {

    public List<List<Integer>> generate(int numRows) {

        

        List<List<Integer>> triangle = new ArrayList<>(); //created empty List of lists

        

        if(numRows==0)

            return triangle;

        

        

        List<Integer> first_row = new ArrayList<>(); //created first row 

        first_row.add(1); // and assigned 1 to first row

        

        triangle.add(first_row); //adding first row to our List of lists

        

        

        //Looping through each row

        for(int i=1;i<numRows;i++){

            List<Integer> prev_row=triangle.get(i-1); //retreiving previous row from triangle

            List<Integer> row = new ArrayList<>(); // creating an empty row to fill each element in this row

            

            row.add(1); // adding 1 at first as 1 is the first element for every row

            

            for(int j=1;j<i;j++){

                row.add(prev_row.get(j-1)+prev_row.get(j)); // summing up elements in previous row and filling in the row   

                

            }

            

            row.add(1); // adding 1 to row as last element for every row is 1

            triangle.add(row); // Now adding the row to List of lists

            

        }

        

        return triangle;

        

    }

}

Output:

Your input
5
Output
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Expected
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Contains Duplicate - LeetCode 217

 Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.


Example 1:

Input: nums = [1,2,3,1]
Output: true

Example 2:

Input: nums = [1,2,3,4]
Output: false

Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true

Solution:

import java.io.*;

import java.util.*;

public class Main

{

    static Scanner sc=new Scanner(System.in);

public static void main(String[] args) {

    

    int n;

    n=sc.nextInt();

    int[] arr=new int[n];

    for(int i=0;i<n;i++){

        arr[i]=sc.nextInt();

    }

    Solution s=new Solution();

    boolean res=s.containsDuplicate(arr);

    System.out.println(res);

}

}


public class Solution {

  

   public boolean containsDuplicate(int[] nums) {

        

        HashSet<Integer> hashset = new HashSet<>();

        

        for(int i=0;i<nums.length;i++){

            if(hashset.contains(nums[i]))

                return true;

            

            hashset.add(nums[i]);

        }

        

        return false;

    }

}


Your input
[1,2,3,1]
Output
true
Expected
true

Sunday, 18 July 2021

Calculating sum of digits using Recursion

Input: 253

Output: 10 
(we need to add the individual digits in the number) 


Source code:

import java.util.*;

import java.io.*;



public class Main

{

public static void main(String[] args) 

{

    Scanner s=new Scanner(System.in);

    System.out.println("Enter number");

    Long n =s.nextLong();

System.out.println("Answer: "+sumOfDigits(n));

}

public static Long sumOfDigits(Long n)

{

    if(n==0)

        return 0L;

        

    return (n%10)+sumOfDigits(n/10);

}

}

Output:

Enter number

1155588

Answer: 33

Palindrome Check using Recursion

 Problem: 

You are given a String 'S'. You need to recursively find the if the string is Palindrome or not.

Test case 1: 

Input: abba

Output: True

Test case 2: 

Input: abbcbba

Output: True

Test case 3: 

Input: abbad

Output: False

Source code:


import java.util.*;

import java.io.*;



public class Main

{

    static int k=1;

public static void main(String[] args) 

{

    Scanner s=new Scanner(System.in);

    System.out.println("Enter String");

    String str =s.next();

System.out.println("Answer: "+isPalindrome(str,0,str.length()-1));

}

public static boolean isPalindrome(String str,int start,int end)

{

    if(start>=end)

        return true;

        

    return ((str.charAt(start)==str.charAt(end)) && isPalindrome(str,start+1,end-1));

}

}





 

Thursday, 31 December 2020

Union of Two arrays.

Given two different sorted arrays. We need to print union of two arrays. ( Elements which are common in both the arrays)

arr1={1,3,4,5,7}

arr2={2,3,5,6}

Output: {1,2,3,4,5,6,7}

Source code:


public class Main
{
public static void main(String[] args)
{
int arr1[]={1,3,4,5,7};
int arr2[]={2,3,5,6};
union(arr1,arr2);
}
public static void union(int arr1[],int arr2[])
{
int i=0,j=0;

while(i<arr1.length&&j<arr2.length)
{
if(arr1[i]<arr2[j])
{
System.out.print(arr1[i]+" ");
i++;
}
else if(arr1[i]>arr2[j])
{
System.out.print(arr2[j]
+" ");

j++;
}
else if(arr1[i]==arr2[j])
{
System.out.print(arr1[i]
+" ");

i++;
j++;
}
}

while(i<arr1.length)
System.out.print(arr1[i++]
+" ");

while(j<arr2.length)
System.out.print(arr2[j++]
+" ");

}
}

Monday, 28 December 2020

Initializing a string with repeated character of specific length

Source code:

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args) 

{

   char c='0';

            int n=10;

  char ch[]=new char[n];

  Arrays.fill(ch,c);

  String s=new String(ch);

  System.out.println(s);   

}

}

output:
0000000000

Sunday, 27 December 2020

Minimum flips required to get given binary String.

Given a string S, the task is to find minimum flips required to convert an initial binary string consisting of only zeroes to S where every flip of a character flips all succeeding characters as well.

Input: S = “01011”
Output: 3
Explanation:
Initial String – “00000”
Flip the 2nd bit – “01111”
Flip the 3rd bit – “01000”
Flip the 4th bit – “01011”
Total Flips = 3
Input: S = “01001”
Output: 3
Explanation:
Initial String – “00000”
Flip the 2nd bit – “01111”
Flip the 3rd bit – “01000”
Flip the 5th bit – “01001”
Total Flips = 3

Source Code:

public class FlipDigitsOfStringToGetTarget {

public static void main(String[] args) {

String target="01011";
int n=target.length();
System.out.print("Minimum flips required: "+minFlips(target,n));

}
public static int minFlips(String target,int n)
{
int count=0;
char curr='1';

for(int i=0;i<n;i++)
{
char ch=target.charAt(i);

if(ch==curr)
{
++count;
curr=(char)(48+(curr%2));
}
}
return count;
}

}

Sunday, 20 December 2020

Anagram Check of 2 strings

Given a program to check whether two strings are anagram or not. 

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 Example 1:

SILENT

LISTEN

Example 2:

aab

aba

In the above case both strings have same number of characters(characters used exactly once).


Solution:

Approach 1:
Time Complexity: O(n2)

Source code:

public class Main {
public static void main(String[] args)
{
String s="aaab",s2="abba";
boolean isAnagram=false,visited[]=new boolean[s2.length()];
if(s.length()==s2.length())
{
for(int i=0;i<s.length();i++)
{
char ch=s.charAt(i);
isAnagram=false;
for(int j=0;j<s2.length();j++)
{
if(s2.charAt(j)==ch&&visited[j]==false)
{
isAnagram=true;
visited[j]=true;
break;
}
}
if(!isAnagram)
break;
}
}
if(isAnagram)
System.out.println("Anagram");
else
System.out.println("Not an Anagram");
}
}

Approach 2:

Taking two 256 arrays and making a note of count at its respective indices.
Eg: if 'a' is encountered then index at 97 is increased.

public class Main
{
public static void main(String[] args)
{
String a="aab";
String b="aba";
boolean isAnagram=true;
int[] al=new int[256];
int[] bl=new int[256];

for(char c:a.toCharArray()){
int index=(int)c;
al[index]++;
}
for(char c:b.toCharArray()){
int index=(int) c;
bl[index]++;
}
for(int i=0;i<256;i++){
if(al[i]!=bl[i]){
isAnagram=false;
break;
}
}
if(isAnagram)
System.out.println("Anagram");
else
System.out.println("Not an anagram");
}
}



Approach 3:

Taking one integer array and when character encountered in first string the increment and after iterating second string decrement the same index. At last check whether all the elements in array are zeros.

public class Main
{
public static void main(String[] args)
{
String a="aab";
String b="aba";
boolean isAnagram=true;
int[] al=new int[256];

for(char c:a.toCharArray()){
int index=(int)c;
al[index]++;
}
for(char c:b.toCharArray()){
int index=(int) c;
al[index]--;
}
for(int i=0;i<256;i++){
if(al[i]!=0)
{
isAnagram=false;
break;
}
}
if(isAnagram)
System.out.println("Anagram");
else
System.out.println("Not an anagram");
}
}



Sunday, 26 May 2019

Maximum in sub-arrays of length K:

Given an array of integers and a number k, where 1 <= k <= length of the array, compute the maximum values of each subarray of length k.

For example, given array = [10, 5, 2, 7, 8, 7] and k = 3, we should get: [10, 7, 8, 8], since:

10 because {10,5,2} (10 is maximum in sub array)
7   because {5,2,7} (7 is maximum in sub array)
8   because {2,7,8} (8 is maximum in sub array)
8   because {7,8,7} (8 is maximum in sub array)

Imput :
first line of  input contains integer N,
second line of input contains array of integers of length N;
third line of input contains integer K,the length of sub array

Output:
otuput consists of an array of maximum numbers of each subarray.

Program Code:

#include <stdio.h>
int main()
{
    int k,n,a[100],ind=0;
    int i,j,max[100],h,m;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&k);
    h=k;
    for(i=0;i<=n-k;i++)
    {
        
        m=a[i];
for(j=i+1;j<h;j++)
        {
if(a[j]>m)
            {
m=a[j];
            }
        }
        max[i]=m;
        h++;
    }
    
    for(i=0;i<=n-k;i++)
    {
printf("%d ",max[i]);
    }

    return 0;
}

Random password generator in Java

       Random password generator in Java Source code: mport java.io.*; import java.util.*; public class Main { public static void main(Str...