Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Post a Comment

HackerRank Hiring Contest

Q - 1  Programming Competition


 Question URL


 Solution :-
public class Solution {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
        int n = Integer.parseInt(br.readLine());
        ArrayList<String> name = new ArrayList<>();
        int index = 0;
        int val = Integer.MIN_VALUE;
   
        for(int i = 0;i<n;i++){
            String vals[] = br.readLine().split(" ");
       
            name.add(vals[0]);
            int tmpVal = Math.abs(Integer.parseInt(vals[1])-Integer.parseInt(vals[2]));
       
            if(val<tmpVal){
                val = tmpVal;
                index = i;
            }
        }
        System.out.println(name.get(index)+ " " +val);
    }
}


Q-2 Winning Lottery Ticket

Question URL
Solution :-

public class Solution {    public static void main(String[] args)throws IOException {
   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   
        int n = Integer.parseInt(br.readLine());
   
        HashSet<Character> set[] = new HashSet[n];
   
        for(int i = 0 ; i < n ; i++){
            String line = br.readLine();
            set[i] = new HashSet<>();
       
            for(int j =0 ; j < line.length() ; j++){
                set[i].add(line.charAt(j));
            }
        }
        long ans = 0;
        for(int i = 0 ; i < n ; i++ ){
       
            ArrayList<Character> rem = new ArrayList<>();
            for(int l = 48 ; l < 58 ; l++){
                    if(!set[i].contains((char)l)){
                        rem.add((char)l);
                    }
            }
            //System.out.println(rem);
       
            if(rem.size()==0){
                    ans += n-i;
                    ans--;
                    continue;
            }
       
            for(int j = i+1 ; j < n ; j++ ){
           
                boolean status =true;
           
                for(int l = 0; l < rem.size(); l++){
                    if(!set[j].contains(rem.get(l))){
                       status = false;
                        break;
                    }
                }
                /*for(int l = 48 ; l < 58 ; l++){
                    if(set[i].contains((char)l) || set[j].contains((char)l)){
                   
                    } else {
                        status = false;
                        break;
                    }
                }*/
           
                if(status){
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

Comments

Post a Comment

Popular posts from this blog

Array Transformation | biweekly-contest-12 | leetcode | Java Solution

Question Source Java Solution: class Solution {     public List<Integer> transformArray(int[] arr) {                  while(true) {             boolean isChanged = false;             int []copy = arr.clone();                          for(int i = 1; i < arr.length-1; i++) {                                 if(arr[i-1] > arr[i] && arr[i+1] > arr[i]) {                      copy[i]++;                     isChanged = true;                 }else if(arr[i-1] < arr[i] && arr[i+1] < arr[i]) {               ...
Read more

Dynamic Programming: Basics and a Practical Example

Introduction: Dynamic programming is a problem-solving technique that can seem quite intimidating at first glance. However, once you grasp its fundamentals and see it in action, you'll find it to be a powerful tool in your coding arsenal. In this blog post, we'll demystify the basics of dynamic programming and walk through a practical example. We'll provide you with clear explanations and a complete Python program, so you can understand and apply this essential concept with confidence. Understanding Dynamic Programming: At its core, dynamic programming is all about breaking down a complex problem into smaller, overlapping subproblems. It's a technique used to efficiently solve problems by storing and reusing solutions to these subproblems, rather than recomputing them. This leads to significant improvements in runtime complexity. Example: Fibonacci Sequence with Dynamic Programming Let's start by tackling a classic problem: calculating Fibonacci numbers. The Fibonac...
Read more

leetcode | Longest Substring Without Repeating Characters Solution

Source Problem: Given a string, find the length of the  longest substring  without repeating the characters. Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. Solution: class Solution {     public int lengthOfLongestSubstring(String s) {                  Set<Character> subStr = new HashSet<>();         int maxLength = 0;         int j = 0;         for(int i = 0; i < s.length(); i++) {                          if(subStr.contains(s.charAt(i))){ ...
Read more