Quiz 19: Explain insertion sort step by step

Problem:

Explain insertion sort step by step ie printing each step line by line

Input Format: 
unsorted array

Output Format: 
sorted array

Constraints: 
none

Sample Input

8 1 4 -2 6 3

Sample Output:
1 8 4 -2 6 3
1 4 8 -2 6 3
-2 1 4 8 6 3
-2 1 4 6 8 3
-2 1 3 4 6 8

Explanations:-

Insertion sort will first sort first 2 elements, then 1st 3, then 1st 4 and so on

---

Solution:

chomp($str=<STDIN>);
@arr =split(" ",$str);
$len=@arr;
for($i=1;$i<$len;$i++)
{
$x = $arr[$i];
$j=$i-1;
while($j>=0 and $x<$arr[$j])
{
$tmp=$arr[$j];
$arr[$j]=$x;
$arr[$j+1]=$tmp;
$j--;
$c++;
}
foreach(@arr)
{
print "$_ ";
}
print "\n";
}

---

Tips:

Insertion sort is efficient for small set of data only. For bigger set, select some other sort algorithm.

Quiz 18: Find number of chocolates in exchange of wrappers

Problem:

A boy have $N money in his pocket. The price of each chocolate is $C. The store offers a discount: for every M wrappers he gives to the store, he gets one chocolate for free. How many chocolates does boy get to eat?

Input Format: 
The first line contains the number of test cases T(<=1000). 
T lines follow, each of which contains three integers N, C and M

Output Format: 
Print the total number of chocolates Boy eats.

Constraints: 
2≤N≤105 
1≤C≤N
2≤M≤N

Sample Input

3

6 2 2

8 3 4

20 2 2

Sample Output:

5

2

19

Explanations:-

case 1, With 6$, he gets 3 chocolates. So he have 3 wrappers. He exchange 2 wrappers out of 3 to get 4th chocolate and now he have a new wrapper from the 4th chocolate, so total wrappers are 2. He again exchanges them and get 5th chocolate. So answer is 5.

---

Solution:

chomp($t=<STDIN>);
@output=();
if($t>1000)
{
exit;
}
for($i=0;$i<$t;$i++)
{
chomp($line=<STDIN>);
@arr=split(" ",$line);
if($arr[0]<2 or $arr[0]>100000 or $arr[1]<1 or $arr[1]>$arr[0] or $arr[2]<2 or 

$arr[2]>$arr[0])
{
exit;
}
$c=$arr[0]/$arr[1];
$c= int $c;
$w=$c;
while($w >= $arr[2])
{
$c1=$w/$arr[2];
$c1= int $c1;
$c= $c+$c1;
$w=$w%$arr[2]+$c1;
}
push(@output,$c);
}
foreach(@output)
{
print "$_\n";
}

---

Tips:

Dont forget to round off number of chocolates, like with$7, if cost of each chocolate is $2, you will get 3 chocolates and not 3.5

Quiz 17: Find average number of balls in each jar

Problem:

There are N empty candy jars, numbered from 1 to N, with infinite capacity. M operations are performed. Each operation is described by 3 integers a, b and k. Here, a and b are index of the jars, and k is the number of candies to be added inside each jar whose index lies between a and b (both inclusive). Can you tell the average number of candies after M operations?

Input format

The first line contains two integers N and M separated by a single space.

M lines follow. Each of the M lines contain three integers a, b and k separated by single space.

Output Format

A single line containing the average number of candies across N jars, rounded down to the nearest integer.

Note 

Rounded down means finding the greatest integer which is less than or equal to given number. Eg, 13.65 and 13.23 is rounded down to 13, while 12.98 is rounded down to 12.

Constraints

3 <= N <= 10000000

1 <= M <= 100000

1 <= a <= b <= N

0 <= k <= 1000000

Sample Input
4 2
1 4 100
2 3 50

Sample Output:
125

Explanations:-
balls initially in 4 jars 0,0,0,0
1st operation -> 100,100,100,100
2nd operation->100,150,150,100
average = 500/4=125

---

Solution:

chomp($line1 =<STDIN>);
@line = split(" ",$line1);
$n = $line[0];
$m = $line[1];
if($n<3 or $n>10000000 or $m<1 or $m>100000)
{
exit;
}
$output = 0;
$tmp=0;
for($i=0;$i<$m;$i++)
{
chomp($line2 = <STDIN>);
        @op = split(" ",$line2);
if($op[0]<1 or $op[0]>$op[1] or $op[1]<1 or $op[1]>$n or $op[2]<0 or 

$op[2]>1000000)
{
exit;
}
        $tmp=$op[2]*($op[1]-$op[0]+1);
$output=$output+$tmp;
}
$output = $output/$n;
$output = int $output;
print "$output";

---

Tips:
Use int $string to round off to nearest interger, note 6.67 will return 6 and not 7.

Quiz 16: Find if a string can be converted to palindrome or not

Problem:
There is a string having lower case english alphabets only. Find out if the string can be changed into palindrome by rearranging alphabets.

Constraints
1<=length of string<=100000
String contains only lower case english language alphabets

Sample Input
poiuytrecwkqgqlpowieurytaaaxxckla

Sample Output:
poiuytrecwkqgqlpowieurytaaaxxckla can be converted to palindrome

Explanations:-
String can be changed to "poiuytrecwkqlaaxgxaalqkwrectyuiop" which is a palindrome

---

Solution:

chomp($a =<STDIN>);
@output;
$odd=0;
@arr = split("",$a);
@arr = sort(@arr);
$len = @arr;
if($len<1 or $len > 100000)
   {
   exit;
   }
foreach(@arr)
{
$ascii = ord($_);
if($ascii<97 or $ascii > 122)
   {
   exit;
   }
}
my $tmp = 1;
for(my $i=0;$i<@arr;$i++)
  {
  if($arr[$i] eq $arr[$i+1])
       {
       $tmp++;
       }
   else{ 
       push(@output,$tmp);
       $tmp = 1;
       }
   }
for(my $j=0;$j<@output;$j++)
{
if($output[$j] % 2 == 0)
   {
   }
   else
   {
   $odd++;
   }
if($odd > 1)
{
print "$a cannot be converted to palindrome";
exit;
}
}
print "$a can be converted to palindrome";

---

Tips:
Each alphabet should occur even number of times, only 1 alphabet can occur odd number of times which can be in middle of string.

Quiz 15: Find all possible values for last ball

Problem:
There are N number of balls having numbers on them. Number of 1st ball is 0. Number of next ball is either +a or +b then previous ball. Number of next ball is again either +a o +b then previous ball. Find all possible values for last ball(in increasing order) seperated by space
Input is in form of 3 lines
N= no of balls
a
b

Constraints
1<=N,a,b<=15
a != b

Sample Input
4
100
10

Sample Output:
30 120 210 300

Explanations:-
possible series
0 10 20 30
0 10 20 120
0 10 110 120
0 10 110 210
0 100 110 120
0 100 110 210
0 100 200 210
0 100 200 300
so last ball number can be 30,120,210 or 300

---

Solution:

@output = ();
chomp($n=<STDIN>);
if($n<1 or $n>1000)
{
exit;
}
chomp($a=<STDIN>);
if($a<1 or $a>1000)
{
exit;
}
chomp($b=<STDIN>);
if($b<1 or $b>1000)
{
exit;
}
if($a == $b)
{
exit;
}
$o1 = $a*($n-1);
$t1= $b*($n-1);
$x=($t1-$o1)/($n-1);
for($j=0;$j<$n;$j++)
     {
      $o2=$o1+($x*$j);
      push(@output,$o2);
     }
@output = sort {$a <=> $b}(@output);
foreach(@output)
{
print "$_ ";
}

---

Tips:
There will be N possible values ranging from a*(N-1) to b*(N-1) having equal difference.
To sort numerically, use sort {$a <=> $b}(@output);

Quiz 14: Find number of positions where digit divides the number

Problem:
Given a number like 1234, you need to find number of digits from number which divides the number.
Like 1234 when divided by 1,2,3,4->exact division is by digits 1,2 only, so output should be 2.
Input is in form of T, where T is number of test cases followed by numbers N

Constraints
1<=T<=15
0<N<10000000000

Sample Input:
3
121
123456789
12021

Sample Output:
2
3
2

Explanations:- T = 3, so 3 test cases. For 121, digits are 1,2,1->out of these only 1,1 exactly divides 121, so output is 2.

---

Solution:

chomp($t=<STDIN>);
if($t<1 or $t>15)
{
exit;
}
$tmp = 0;
@output = ();
for($i=0;$i<$t;$i++)                     #loop for each test case
{
chomp($a=<STDIN>);
if($a<=0 or $a>=10000000000)
{
exit;
}
@arr=split("",$a);
for($j=0;$j<@arr;$j++)
   {
   if($arr[$j] == 0)                    #skipping %0 cases
   {
   next;
   }
   elsif($a%$arr[$j] == 0)          #checking for division
      {
      $tmp++;
      }
   }
push(@output,$tmp);
$tmp = 0;
}
foreach(@output)
{
print "$_\n";
}

---

Tips:
Take care of modulus with 0->it will give runtime error

Quiz 13: Find minimum number of steps to convert a string into palindrome

Problem:
A Palindrome is a string with is exactly same as its reverse string like abcba.
Given a string containing only alphabets from a-z, we have to find minimum number of steps required to convert the string to palindrome.
allowed operations:
- any alphabet can be reduced by 1 lower alphabet in a step like d can be reduced to c
- alphabet a cannot be reduced further

Sample Input:
abcd

Sample Output:
4

Explanations:- step1-> abcd -> abcc
                      step2->abcc->abcb
                      step3->abcb->abca
                      step4->abca->abba-> so 4 steps are required

---

Solution:

chomp($a=<STDIN>);   #take input
@arr=split("",$a);   #convert string to array  
$len = @arr;   #get length of array
$tmp = 0;      #this variable will store our count
for($i=0;$i<$len/2;$i++)
{
$a = ord($arr[$i]);   #ord will get ascii value
$b = ord($arr[$len-$i-1]);
if($a>$b)   #compare characters 
   {
   $tmp = $tmp + $a - $b;
   }
elsif($a<=$b)
   {
   $tmp = $tmp + $b - $a;
   }
}
print "$tmp";

---

Tips:

• compare 1st and last character, then 2nd and last-2 and so on.