manthanthakker40

Number of ways cents combination ( CTCI )

Jan 14th, 2017
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.87 KB | None | 0 0
  1. /*
  2.  * To change this license header, choose License Headers in Project Properties.
  3.  * To change this template file, choose Tools | Templates
  4.  * and open the template in the editor.
  5.  */
  6. package code;
  7.  
  8. import java.util.ArrayList;
  9. import java.util.Arrays;
  10. import java.util.HashMap;
  11. import java.util.LinkedHashMap;
  12. import java.util.LinkedList;
  13. import java.util.List;
  14. import java.util.Scanner;
  15.  
  16. /**
  17.  *
  18.  * @author manth
  19.  */
  20. public class Code {
  21.  
  22.     /**
  23.      * @param args the command line arguments
  24.      */
  25.     /*
  26.     Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
  27.  
  28. Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
  29.  
  30. The order of output does not matter.
  31.  
  32. Example 1:
  33.  
  34. Input:
  35. s: "cbaebabacd" p: "abc"
  36.  
  37. Output:
  38. [0, 6]
  39.  
  40. Explanation:
  41. The substring with start index = 0 is "cba", which is an anagram of "abc".
  42. The substring with start index = 6 is "bac", which is an anagram of "abc".
  43.     */
  44.     static int [][] sc=new int [25][25];
  45.     public static void main(String[] args) {
  46.        Scanner sc1=new Scanner(System.in);
  47.        //String s=sc1.nextLine();
  48.        
  49.        
  50.        
  51.      
  52.        System.out.println(ways(6));
  53.      
  54.        
  55.    
  56.      
  57.        }
  58.    
  59.     static HashMap<Integer,Integer> ways_cents=new HashMap<>();
  60.     public static int ways (int cents)
  61.     {
  62.       if(cents<0)
  63.           return 0;
  64.       if(cents==0)
  65.           return 1;
  66.      
  67.       if(ways_cents.get(cents)!=null)
  68.       {
  69.           return ways_cents.get(cents);
  70.       }
  71.       else
  72.       {
  73.           int count=(ways(cents-25)+ways(cents-10)+ways(cents-5)+ways(cents-1));
  74.           ways_cents.put(cents, count);
  75.           return count;
  76.          
  77.       }
  78.        
  79.     }
  80.    
  81.    
  82.    
  83.    
  84.    
  85.        
  86.        
  87.    
  88.    
  89.    
  90. }
Advertisement
Add Comment
Please, Sign In to add comment