Solutions Of Practice Questions Dated 01-06-2022
Question 1:
Transmit the Message:
Solution:
import java.util.*;
class Solution{
public static void main(String arg[]){
Scanner sc=new Scanner(System.in);
String s=sc.next();
ArrayList<Integer>aa=new ArrayList<Integer>();
ArrayList<Character>ab=new ArrayList<Character>();
char flag=s.charAt(0);
int index=0;
int count=1;
for(int i=1;i<s.length();i++){
if(flag==s.charAt(i)){
count++;
}
else{
aa.add(index,count);
ab.add(index,flag);
count=1;
flag=s.charAt(i);
index++;
}
}
aa.add(index,count);
ab.add(index,flag);
int max=Collections.max(aa);
for(int i=aa.size()-1;i>0;i--){
if(aa.get(i)==max){
flag=ab.get(i);
break;
}
}
StringBuilder sb=new StringBuilder();
for(int i=0;i<max;i++){
sb.append(flag);
}
/*System.out.println(aa);
System.out.println(ab);*/
System.out.println(max);
System.out.println(sb);
}
}
Time Complexity: O(N)
Space Complexity: O(1)[String Is Given]
Auxiliary Space: O(N)[ArrayLists are used.]
Total Test Cases:5
Approach Used:
Here we need to find out the string which is longest in length and appears in the given message.
1. We need to know the cont of different characters so for that we used ArrayList aa of integers that will store occurrence-wise frequency of characters.
2. We need to have a corresponding character value to frequency and for that, we used an ArrayList ab which will store characters.
While traversing we will keep count of characters and store their frequency and character values in arraylists.
eg if string is "aabbcfedeeeeeghirk"
then aa={}(frequency of character)
ab={}(characters)
char flag='a'
int count=1;
if(flag=s.charAt(i))
count++;
else{
//different character
aa.add(index,count)//will store the count of charadter at location index.
ab.add(index,flag)//will store the character at location index
count=1;//making it to default value of count as 1
index++;//index value increase means new location in arraylists
flag=s.charAt(i)//new character will become flag now
}
Question: Why don't we use Map for storing frequency and their corresponding character?
Answer: The reason is if we use a map then they will store the frequency based on all occurrences of characters, not on the longest occurrence.
eq if string is aabrffffaaa then
in hashmap:{a=5,f=4} ans={5,aaaaa} (wrong answer)
in logic above:{a=2, f=4, a=3} ans :{4,ffff} (correct answer)
Question: After the loop also we have written storing condition of count and the corresponding character in ArrayList, Why?
Answer: Because for the last character the comparison will not be done as the string will terminate. So to procure its frequency and char value we stored it in the ArrayList after the termination of the loop.
=========================================================================
Question 1:
Mars Stone:
Solution:
import java.util.*;
class Solution{
public static void main(String arg[]){
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
ArrayList<Integer>aa=new ArrayList<Integer>();
for(int i=0;i<n;i++){
aa.add(sc.nextInt());
}
ArrayList<Integer>ab=new ArrayList<Integer>();
for(int i=1;i<m+1;i++){
ab.add(i);
}
/*System.out.println(aa);
System.out.println(ab);*/
ab.removeAll(aa);
aa.clear();
// System.out.println(ab);
int count=0;
int sum=0;
for(int i=0;i<ab.size()-1;i++){
sum=ab.get(i);
if(sum<m){
count++;
for(int j=i+1;j<ab.size();j++){
sum=sum+ab.get(j);
if(sum<m){
count++;
}
else{
aa.add(count);
count=0;
break;
}
}
}
}
//System.out.println(aa);
if(aa.size()==0){
System.out.println(0);
}
else{
System.out.println(Collections.max(aa));
}
}
}
Time Complexity: O(M*M)[Worst case whole list traversal.]
Space Complexity: O(N)[Array Is Given]
Auxiliary Space: O(N)[ArrayLists are used.]
Total Test Cases:4
Approach Used:
Here first we will store all the values from 1 to m in the ArrayList ab.
Then we will have the input values in ArrayList aa.
We will remove the ArrayList aa from ab as aa contains elements that are common.
After removal, we will declare one sum variable which will store the sum value of elements in the list ab and clear up ArrayList aa(making it ready for further storage).
We will traverse the list and keep on maintaining the sum value.
If sum value < m then count++
else
aa.add(count)
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment