Quiz 50: Solve the equation

Problem:

Given a equation with operations +,-,* only, You have to find the answer.
Start reading the equation from the right and move towards the left.
So, 1*2+3=>1*5=>5

Input Format: 

Test case number T
Next T lines having an equation

Output Format: 
Solution in each line

Constraints: 
Each operand is single digit number.

Sample Input

3
2+4*8-6
2*2*2-2+8
0+0+0+0+3*2

Sample Output:
-6
32
6

Explanations:
2+4*8-6=2+4*-2=2+-8=-6

---

Solution:

chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($tmp=<STDIN>);
@arr=split(//,$tmp);
$len=@arr;
if($len == 1)
{
push(@out,$arr[0]);
next;
}
$len--;
for($j=$len;$j>=0;$j--)
{
($a,$b,$c)=($arr[$j],$arr[$j-1],$arr[$j-2]);
if($b eq '+')
{
$ans=$a+$c;
}
elsif($b eq '-')
{
$ans=$a-$c;
}
if($b eq '*')
{
$ans=$a*$c;
}
$arr[$j-2]=$ans;
$j--;
}
push(@out,$a);
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

operate 3 elements of array, get result , then operation it with next 2 elements and so on

Quiz 49: Find the subset with minimum- Max(subset)-Min(subset)

Problem:

Given T number, you have to select N numbers such that Max(Selection)-Min(Selection) is minimum. Print Max(Selection)-Min(Selection)
ex: if T=3 and N=2 and numbers are 1,2,4 , then selection can be (1,2) or(2,4) or (1,4).
max(1,2)-min(1,2)=2-1=1
max(2,4)-min(2,4)=4-2=2
max(1,4)-min(1,4)=4-1=3
Clearly 1 is minimum, so output should be 1.

Input Format: 

Total number T
Subset number N
next T lines having numbers

Output Format: 
Max(Selection)-Min(Selection)

Constraints: 
none

Sample Input

7
3
2
6
10
12
4
11
16

Sample Output:
2

Explanations:
We have to select 3 numbers from 7 numbers- 2,6,10,12,4,11,16.
We should select 10,11,12. Max(10,11,12)=12. Min(10,11,12)=10. Diff=2. All other possible combinations have difference more than 2.

---

Solution:

chomp($t=<STDIN>);
chomp($n=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($tmp=<STDIN>);
push(@arr,$tmp);
}
@arr=sort{$a<=>$b}@arr;
$ans=$arr[$t-1];
$up=$t-$n;
for($i=0;$i<=$up;$i++)
{
$t=$arr[$i+$n-1]-$arr[$i];
if($t<$ans){$ans=$t;}
}
print $ans;

---

Tips:

Sort all numbers and then calculate for all possible orders using sorted list

Quiz 48: next different alphabet

Problem:

Given a string, you need to convert to a different string such that consecutive characters should be different. Only operation allowed is to delete any alphabet of string. Find minimum number of deletion required

Input Format: 

number of test cases T
next T lines contains a string to be tested

Output Format: 
Minimum number of deletion required

Constraints: 
none

Sample Input

3
ababa
aaaabbbb
acbbca

Sample Output:
0
6
1

Explanations:
ababa already have proper condition.
aaaabbbb = ab, so 3 a and 3 b deleted, so ans is 3+3=6
acbbca = acbca, so only 1 b need to be deleted

---

Solution:

chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($s=<STDIN>);
@arr=split("",$s);
$len=@arr;
$len--;
$ans=0;
for($j=0;$j<$len;$j++)
{
if($arr[$j] eq $arr[$j+1])
{
$ans++;
}
}
push(@out,$ans);
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

just increment counter if neighbours are same.

Quiz 47: Find maximum value of XOR

Problem:

Given 2 number, find maximum XOR between them

Input Format: 

num 1
num 2

Output Format: 
Max XOR

Constraints: 
none

Sample Input

5
6

Sample Output:
3

Explanations:
5 XOR 5=0
5 XOR 6=3
6 XOR 6=0, so max is 3.

---

Solution:

chomp($a=<STDIN>);
chomp($b=<STDIN>);
$c=0;
for($i=$a;$i<=$b;$i++)
{
for($j=$i;$j<=$b;$j++)
{
$tmp=$i ^ $j;
if($tmp>$c)
{
$c=$tmp;
}
}
}
print $c;

---

Tips:

Find XOR for all possible combinations and print highest among them

Quiz 46: Find if given number is a Fibonacci number

Problem:

Given a number, determine if it is Fibonacci or not.

Input Format: 

t=number of test cases
followed by t lines having 1 number

Output Format: 
Yes or No for each input

Constraints: 
none

Sample Input

4
8
75025
80000
11111

Sample Output:
Yes
Yes
No
No

Explanations:
series is 0, 1, 1, 2, 3, 5, 8, 13......

---

Solution:

chomp($n=<STDIN>);
for($i=0;$i<$n;$i++)
{
chomp($s=<STDIN>);
$a=(5*$s*$s);
$b=$a+4;
$b=sqrt($b);
$c=int($b);
$d=$a-4;
$d=sqrt($d);
$e=int($d);
if($b == $c or $d == $e)
{
push(@out,'Yes');
}
else
{
push(@out,'No');
}
}
foreach(@out)
{
print "$_\n";
}

---

Tips:

Simple logic- check if 5*num*num+4 or 5*num*num-4 is a perfect sqaure.

Quiz 45: Determine whether number is prime or not

Problem:

Given a number, determine if it is prime or not.

Input Format: 

t=number of test cases
followed by t lines having 1 number

Output Format: 
YES or NO for each input

Constraints: 
none

Sample Input

4
6
1333
45611
5179

Sample Output:
NO
NO
NO 
YES

Explanations:
6 is not prime since can be dived by 2 and 3. 5179 is prime since can be divided by 1 and 5179 only and no other number

---

Solution:

sub prime {
    my $number = shift;
    my $str = 2;
    my $sqrt = sqrt $number;
    while(1) {
        if ($number%$str == 0) {
            return 'NO';
        }
        if ($str < $sqrt) {
            $str++;
        } else {
            return 'YES';
        }
    }
}
chomp($t=<STDIN>);
for($i=0;$i<$t;$i++)
{
chomp($n=<STDIN>);
push(@out,prime($n));

}
foreach(@out)
{
print "$_\n";
}

---

Tips:

Check the function used to determine prime number

Quiz 44: Find the next bigger number with same bits

Problem:

Given a decimal number, find the next bigger decimal number having same numbers of 1's and 0's in binary format as original number. like 11011 and 11110 have same number of 1's and 0's.

Input Format: 

t=number of test cases
followed by t lines having a decimal number

Output Format: 
next big decimal number for each input in new line

Constraints: 
none

Sample Input

2
21
44

Sample Output:
22
49

Explanations:
for case 2, 44 in binary is 101100 have 3 1's and 3 0's, next bigger number with same bits is 110001 ie 49.

---

Solution:

$n=<STDIN>;
while($n>0)
{
$a=<STDIN>;
$b=sprintf("%b",$a);
$b='0'.$b;
$b=~s/(.*)01(.*)/$1 10 $2/;
$q=join '',sort split('',$2);
$b=~s{(.*)$2}{$1$q};
$b=~s/\s//g;
$x=oct("0b".$b);
push(@o,$x);
$n--;
}
foreach(@o)
{
print"$_\n";
}

---

Tips:

Next bigger number is formed by finding first 01 from the right and replacing it by 10 , then arranging remaining characters on right to make it minimum, like 1010 to 0011.