0% found this document useful (0 votes)

10 views17 pages

Special Sum and Rhyme Finder Algorithms

Q: How does the approach to finding the most popular code from sentences ensure accuracy, and what transformations are applied?

The approach ensures accuracy by extracting the first and last letter of each word in a sentence to form codes and using these codes to find the one that occurs most frequently. The transformations applied include splitting the sentence into words, forming codes by concatenating the first and last characters, storing these in a map with their frequencies, and then identifying the code with the maximum count using a max function over the entries in the map. This structured method of processing and counting ensures that the resultant most popular code is accurately determined .

Q: How do you calculate a special sum for an array based on the given rules, and what is the approach used in the code provided?

To calculate the special sum for an array, the code iterates through each element of the array and computes a start index using the formula start = max(0, i-arr[i]) for an element at index i. It then sums up the elements from this start index to the current index i, inclusive, and adds this sum to a total sum. The approach, implemented in the Java code, involves initializing a total sum to zero, then updating it by iterating over each index of the array to apply the described rule and accumulate the results into the total sum .

Q: What logic is used to determine the best rhyming word from a dictionary, and how does the implementation ensure optimality?

The logic for determining the best rhyming word involves comparing the ending characters of the input string and each word in the dictionary. The code matches characters starting from the last until a difference is found. The word with the highest number of matching consecutive characters is deemed as rhyming the best. This is implemented by iterating over every word, except the input word, and keeping track of the maximum consecutive matches using a LinkedHashMap to store counts. Optimality is ensured by checking all words and selecting the one with the highest count of matching characters .

Q: In what way does the program compute the largest difference between fruit frequencies in a string, and what does it signify?

The program computes the largest difference between fruit frequencies by first counting the frequency of each character using a HashMap, distinguishing between odd and even frequencies. It then finds the maximum value among the odd frequencies and the minimum value among the even frequencies. The largest difference signifies the absolute difference between these two extremes, which reflects the range within which fruit frequencies vary when categorized by evenness and oddness in the count .

Q: What approach is used to determine the bitwise OR of two integers, and what is a practical example?

The approach uses the bitwise OR operator, which compares the binary form of two integers such that for each bit pair in the same position in the two numbers, the result has a bit set to 1 if at least one of the bits in the pair is 1. A practical example is computing the bitwise OR of 5 (binary '101') and 3 (binary '011'), resulting in 7 (binary '111').

Q: What method is used to filter and return unique elements from a list of integers, and how does it manage duplicates?

The method filters unique elements by counting occurrences of each integer in the list using nested loops. If an integer occurs exactly once, it is considered unique and added to a result list. The method ensures duplicates are identified and not added to the result by using a count variable within a loop comparing each element with every other element .

Q: Describe the criteria and computation method for identifying magical numbers in a numeric range. What implications does this have for data representation?

Magical numbers are identified by converting integers within a range to binary, altering this binary string by replacing '0' with '1' and '1' with '2', then summing the modified binary digits. If the sum is odd, the number is magical. This computation highlights the impacts of binary representation on numerical properties, showing how simple bit manipulations affect interpretations, such as determining magical numbers based on modified binary characteristics .

Q: How does the code handle identifying numbers in a list based on a modular arithmetic condition, and what is a sample scenario for its use?

The code identifies numbers in a list that satisfy the condition val = d*q + r by iterating over the array of numbers and checking if this calculated value matches any of the numbers. This condition leverages modular arithmetic where val is the result of the input values for d, q, and r. A sample scenario is identifying the index of a number which corresponds to 24 when using a divisor of 8 and an additional component of 3 in the list {12,24,35,9} resulting in the number 24 at index 1 matching the equation .

Q: In the context provided, explain how the sum of prime numbers up to a given number is computed and its importance.

The sum of prime numbers up to a given number is computed by iterating through numbers starting from 2 (first prime), checking if each is prime by ensuring no divisor less than its square root exists, and adding it to a total sum if it is prime. This computation is vital for understanding prime distributions and the additive properties of numbers, facilitating analyses in fields like cryptography and number theory .

Q: How does the program calculate the count of substrings in a string, and what does a sample output look like?

The program calculates the count of substrings by iterating through the string and comparing each substring of the same length as the searched substring to find matches. It increments a count each time a match is found. For instance, in the string 'ABCBCAB', searching for the substring 'AB' results in 2 because 'AB' appears twice in the string .

The document contains multiple programming tasks and their corresponding Java code implementations. Each task involves different algorithms such as calculating special sums, finding rhyming words, determining bitwise operations, and counting substrings. The tasks are accompanied by sample inputs and outputs to illustrate the expected results.

Uploaded by

21CSE011 Hirthikha K

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

10 views17 pages

Special Sum and Rhyme Finder Algorithms

Uploaded by

21CSE011 Hirthikha K

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

1. You are given an integer n and an array arr[] of size n.

you need to calculate a special sum

using the following rule:
For each index i (0-based indexing):
[Link] start = max(0,i-arr[i])
[Link] all elements from arr[start] to arr[i] (inclusive) to the total sum
[Link],print the total sum

Sample input-output (1):

Input :

1234

Output :

Sample input-output (2):

Input :

102

Output :

Test Case 3 (All zeros)

Input

5
0 0 0 0 0

Output

Test Case 4 (Mixed values)

Input

5
2 1 3 1 2

Output

Test Case 5 (Single element)

Input

1
5

Output

Test Case 6 (Decreasing values)

Input

5
3 2 1 0 1

Output

CODE :

import [Link].*;
class Main {
public static void main(String[] args) {
Scanner scan = new Scanner ([Link]);
[Link]("Enter the size of an array : ");
int n = [Link]();
[Link]("Enter the array elements : ");
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i]=[Link]();
}
int totSum = 0;
for(int i=0;i<[Link];i++){
int start = [Link](0,i-arr[i]);
int sum = 0;
for(int j=start;j<=i;j++){
sum+=arr[j];
}
totSum+=sum;
}
[Link]("total sum : "+totSum);
}
}

2. A poet has asked you find assistance in writing [Link] has given you a string S and
a dictionary D and he asks you to find ,from the dictionary,a word which rhymes best
with S. words are said to rhyme when the last syllables of the words are the same,like
“cave” and “gave” , or “typical” and “critical”. The words will be deemed to rhyme
best if the last few characters of the words match the most.

Your task is to find and return a string value denoting the word which rhymes best
with S,from dictionary [Link] no such word is found,return the string “No Word”

Input Specification :
Input1 : A string value S,representing a single word
Input2 : A string array D,representing the dictionary
Input3: An integer vlue representing the length of array D

Sample Test Case – 1:

Input1:thunder
Input2: {puzzle,thunder,powder,blender,under}
Input3: 5
Output: under

Sample Test Case – 2:

Input1: cave
Input2: {gave, save, wave, stone}
Input3: 4
Output: gave

Sample Test Case – 3:

Input1: typical
Input2: {critical, logical, physical, digital}
Input3: 4
Output: critical

CODE : - WAY 1

import [Link].*;
class Main {
public static void main(String[] args) {
Scanner scan = new Scanner ([Link]);
[Link]("Enter the size of an array : ");
int n = [Link]();
[Link]();
[Link]("Enter the array elements : ");
String words[] = new String[n];
for(int i=0;i<n;i++){
words[i]=[Link]();
}
[Link]("Enter the rhyme word : ");
String rhyme = [Link]();
Map<String,Integer> map = new LinkedHashMap<>();
for(int i=0;i<[Link];i++){
String word = words[i];
if(![Link](rhyme)){
int count = 0;
for (int j = [Link]() - 1, k = [Link]() - 1;
j >= 0 && k >= 0;
j--, k--){
if([Link](j)==[Link](k)){
count++;
}
else{
break;
}
}
[Link](word,count);
}
}
[Link]<String,Integer> maxEntry = [Link]()
.stream()
.max([Link]())
.get();
String res_rhyme = [Link]();
int max_count = [Link]();
if(max_count==0){
[Link]("No Word");
}
else{
[Link](res_rhyme);
}
}
}

CODE : - WAY 2

String bestWord = "No Word";

int maxCount = 0;

for (String word : words) {

if (![Link](rhyme)) {
int count = 0;

for (int j = [Link]() - 1, k = [Link]() - 1;

j >= 0 && k >= 0;
j--, k--) {

if ([Link](j) == [Link](k)) {
count++;
} else {
break;
}
}

if (count > maxCount) {

maxCount = count;
bestWord = word;
}
}
}

if (maxCount == 0) {
[Link]("No Word");
} else {
[Link](bestWord);
}

3. Sample Test Case 1 :

Input1: {12,24,35,9}
Input2: 8
Input: 3
Input4: 0
Input5: 4

Output: 1

Explanation:
Here, According to the rule, 24 = 8*3+0 and the index value is 1

Sample Test Case 2 :

Input1: {26,32,41,36}
Input2: 5
Input: 5
Input4: 1
Input5: 4

Output: 0

Explanation:
Here, According to the rule, 26 = 5*5+1 and the index value is 0

CODE :

import [Link].*;
class Main {
public static void main(String[] args) {
Scanner scan = new Scanner ([Link]);
[Link]("Enter the size of an array : ");
int n = [Link]();
[Link]("Enter the array elements : ");
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i]=[Link]();
}
[Link]("Enter the value of D : ");
int d = [Link]();
[Link]("Enter the value of Q : ");
int q = [Link]();
[Link]("Enter the value of R : ");
int r = [Link]();
int val = (d*q)+r;
int res_ind=0;
for(int i=0;i<[Link];i++){
if(val==arr[i]){
res_ind = i;
break;
}
}
[Link](res_ind);
}
}

4. Fruit Frequency
You are given a String S containing fruits,where each character represents a fruit
[Link] task is to find and return an integer value representing the largest absolute
difference between the count of the fruit with maximum odd frequency and the count
of the fruit with minimum even frequency.

Sample TestCase – 1:
Input1: aartfu
Output: 1

Sample TestCase – 2:
Input1: aaabbabcdccccd
Output: 3
Explanation :
a => 4,b=>3,c=>5,d=>2.
Maximum odd frequency => 5
Minimum even frequency => 2
Absolute difference =>5-2=3.

CODE : - WAY - 1
import [Link].*;

class Main {
public static int findDifference(String str) {
Map<Character, Integer> freq = new HashMap<>();

// Count frequencies
for (char ch : [Link]()) {
[Link](ch, [Link](ch, 0) + 1);
}
int maxOdd = Integer.MIN_VALUE;
int minEven = Integer.MAX_VALUE;

// Find max odd and min even

for (int count : [Link]()) {
if (count % 2 != 0) { // odd
maxOdd = [Link](maxOdd, count);
} else { // even
minEven = [Link](minEven, count);
}
}

// Edge case safety

if (maxOdd == Integer.MIN_VALUE || minEven == Integer.MAX_VALUE) {
return 0;
}

return [Link](maxOdd - minEven);

}

public static void main(String[] args) {

Scanner scan = new Scanner([Link]);
[Link]("Enter the string:");
String str = [Link]();
[Link](findDifference(str));
}
}
CODE – WAY – 2:
import [Link].*;

class Main {

public static int findDifference(String str) {

int min = Integer.MAX_VALUE; // minimum even frequency

int max = Integer.MIN_VALUE; // maximum odd frequency

for (int i = 0; i < [Link](); i++) {

int count = 0;

// count frequency of current character

for (int j = 0; j < [Link](); j++) {
if ([Link](i) == [Link](j)) {
count++;
}
}

// update max for ODD frequency

if (count % 2 != 0) {
if (count > max) {
max = count;
}
}

// update min for EVEN frequency

if (count % 2 == 0) {
if (count < min) {
min = count;
}
}
}

// if no valid odd or even found

if (max == Integer.MIN_VALUE || min == Integer.MAX_VALUE) {
return 0;
}

return [Link](max - min);

}

public static void main(String[] args) {

Scanner scan = new Scanner([Link]);
[Link]("Enter the string : ");
String str = [Link]();
int val = findDifference(str);
[Link](val);
}
}
5. Imagine you are playing a word game with a sentence
Rule – 1: create code for each word in a sentence
You only care about 2 letters for each word(the very first letter and the very last
letter).
For eg, for the word “good”,the code is “gd”
Rule – 2: Find the most popular code
You have to figure out which code appeared the most times.
Example :
Sentence : apple banana are my favourite fruit anywhere
Output : ae
Explanation :
Codes :
apple=>ae,banana=>ba,are=>ae,my=>my,favourite=>fe,fruit=>ft,anywhere=>ae
Lets count them:
Ae(3 times),ba(1 time),my(1 time),fe(1 time),ft(1 time)

Code “ae” appears most. So “ae” is the output

CODE : WAY – 1:

import [Link].*;
class Main {

public static String findPopularCode(String str) {

String arr[] = [Link](" ");
int len = [Link];
String res="";
int max_index = 0;
for(int i=0;i<len;i++){
char first = arr[i].charAt(0);
char last = arr[i].charAt(arr[i].length() - 1);
res+=""+first+last+" ";
}
int max = Integer.MIN_VALUE;
String codes[] = [Link](" ");
int code_len = [Link];
for(int i=0;i<code_len;i++){
int count = 0;
for(int j=0;j<code_len;j++){
if(codes[i].equals(codes[j])){
count++;
}
}
if(count>max){
max = count;
max_index = i;
}
}
return codes[max_index];
}

public static void main(String[] args) {

Scanner scan = new Scanner([Link]);
[Link]("Enter the string : ");
String str = [Link]();
String val = findPopularCode(str);
[Link](val);
}
}
CODE – WAY – 2:
import [Link].*;

class Main {

public static String findPopularCode(String str) {

String arr[] = [Link](" ");
int len = [Link];
String res="";
int max_index = 0;
for(int i=0;i<len;i++){
char first = arr[i].charAt(0);
char last = arr[i].charAt(arr[i].length() - 1);
res+=""+first+last+" ";
}
int max = Integer.MIN_VALUE;
String codes[] = [Link](" ");
int code_len = [Link];
Map<String,Integer> map = new LinkedHashMap<>();
for(int i=0;i<code_len;i++){
int count = 0;
for(int j=0;j<code_len;j++){
if(codes[i].equals(codes[j])){
count++;
}
}
[Link](codes[i],count);
}
[Link]<String,Integer> maxEntry = [Link]()
.stream()
.max([Link]())
.get();
String popular_code = [Link]();
int max_count = [Link]();
return popular_code;
}

public static void main(String[] args) {

Scanner scan = new Scanner([Link]);
[Link]("Enter the string : ");
String str = [Link]();
String val = findPopularCode(str);
[Link](val);
}
}
CODE WAY – 3:
import [Link].*;

class Main {

public static String findPopularCode(String str) {

String[] arr = [Link](" ");
Map<String, Integer> map = new LinkedHashMap<>();

// create codes and count frequency

for (String word : arr) {
char first = [Link](0);
char last = [Link]([Link]() - 1);
String code = "" + first + last;

[Link](code, [Link](code, 0) + 1);

}

// find max occurring code

return [Link]()
.stream()
.max([Link]())
.get()
.getKey();
}

public static void main(String[] args) {

Scanner scan = new Scanner([Link]);
[Link]("Enter the string : ");
String str = [Link]();
[Link](findPopularCode(str));
}
}

6. You are given a two integers A and B. your task is to find and return an integer
representing the value of their bitwise OR operation
Sample Test Case – 1:
Input1: 5
Input2: 3
Output: 7
CODE :
import [Link].*;
class Main {
public static int findOR(int n1,int n2) {
int res = n1 | n2;
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner([Link]);
[Link]("Enter the first number : ");
int n1 = [Link]();
[Link]("Enter the second number : ");
int n2 = [Link]();
int val = findOR(n1,n2);
[Link](val);
}
}
7. Return the substring count
Sample Test Case – 1:
Input1: ABCBCAB
Input2: AB
Output: 2
CODE :
import [Link].*;
class Main {
public static int findCount(String str,String substring) {
int count = 0;
for(int i=0;i<=[Link]()-[Link]();i++){
if([Link](i,i+[Link]()).equals(substring)){
count++;
}
}
return count;
}
public static void main(String[] args) {
Scanner scan = new Scanner([Link]);
[Link]("Enter the string : ");
String str = [Link]();
[Link]("Enter the substring : ");
String substring = [Link]();
int val = findCount(str,substring);
[Link](val);
}
}
8. Given a list of integers,write a program to print the numbers that occur only once in
the list(unique elements)
Sample Test Case – 1:
Input: [4,5,6,4,7,5,9]
Output: 6 7 9
CODE :
import [Link].*;
class Main {
public static int[] PrintUnique(int arr[]) {
List<Integer> list = new ArrayList<>();
int index = 0;
for(int i=0;i<[Link];i++){
int count = 0;
for(int j=0;j<[Link];j++){
if(arr[i]==arr[j]){
count++;
}
}
if(count==1){
[Link](arr[i]);
}
}
Integer res_list[] = [Link](new Integer[0]);
int len = res_list.length;
int res[] = new int[len];
for(int i=0;i<len;i++){
res[i] = res_list[i];
}
return res;
}
public static void main(String[] args) {
Scanner scan = new Scanner([Link]);
[Link]("Enter the size of an array : ");
int n = [Link]();
[Link]("Enter the array elements : ");
int arr[] = new int[n];
for(int i=0;i<n;i++){
arr[i] = [Link]();
}
int[] val = PrintUnique(arr);
[Link]([Link](val));
}
}
9. You are given a program to find the count of magical numbers from 1 to N. A magical
number is defined by the following criteria:
 Convert each number in the range of 1 to N to its binary representation
 Replace 0 with 1 and 1 with 2 in binary string
 Calculate the sum of all digits in the modified [Link] resultant number is odd
then consider it magical string
You will be given N as input,find out count of all the magical numbers from the range
1 to N.
Sample Test Case – 1:
Input:4
Output:1
Explanation : 1->1->2->even , 1->10->->odd -> magical number , 3->11->4->even ,
4->100->4->even
Sample Test Case – 1:
Input: 5
Output: 2
CODE :
import [Link].*;
class Main {
public static int CountMagicalNumber(int n) {
int count = 0;
for(int i=1;i<=n;i++){
int no = i;
String binary = [Link](no);
String mod_binary = "";
int sum = 0;
for(int j=0;j<[Link]();j++){
if([Link](j)=='0'){
mod_binary+="1";
sum+=1;
}
else{
mod_binary+="2";
sum+=2;
}
}
if(sum%2!=0){
count++;
}
}
return count;
}
public static void main(String[] args) {
Scanner scan = new Scanner([Link]);
[Link]("Enter the size : ");
int n = [Link]();
int val = CountMagicalNumber(n);
[Link](val);
}
}

10. Find the sum of all the prime numbers till the given number N.
Sample Test Case – 1:
Input:10
Output: 17
CODE:
import [Link].*;

class Main {
public static int SumOfPrimes(int n) {
int sum = 0;

for (int i = 2; i <= n; i++) { // primes start from 2

boolean isPrime = true;

for (int j = 2; j * j <= i; j++) {

if (i % j == 0) {
isPrime = false;
break;
}
}

if (isPrime) {
sum += i;
}
}
return sum;
}

public static void main(String[] args) {

Scanner scan = new Scanner([Link]);
[Link]("Enter the size : ");
int n = [Link]();
int val = SumOfPrimes(n);
[Link](val);
}
}
11. You are given a string S in which you have to replace every group of two or more
consecutive identical characters with a string #.If multiple characters appear
consecutively,replace them with a single # as [Link] task is to perform these two
operations and return the final modified string.
Sample Test Case – 1:
Input: aabbbccdeea
Output: #d#a
CODE:

Common questions