Minimum Gift - CodeVita 9 | Zonal Round

 Minimum Gift

A Company has decided to give some gifts to all of its employees. For that, company has given some rank to each employee. Based on that rank, company has made certain rules to distribute the gifts.

The rules for distributing the gifts are:

Each employee must receive at least one gift.

Employees having higher ranking get a greater number of gifts than their neighbours.

What is the minimum number of gifts required by company?

Constraints

1 < T < 10

1 < N < 100000

1 < Rank < 10^9

Input

First line contains integer T, denoting the number of test cases.

For each test case:

First line contains integer N, denoting the number of employees.

Second line contains N space separated integers, denoting the rank of each employee.

Output

For each test case print the number of minimum gifts required on new line.

Example 1

Input

2

5

1 2 1 5 2

2

1 2

Output

7

3

Explanation

For testcase 1, adhering to rules mentioned above,

Employee # 1 whose rank is 1 gets one gift

Employee # 2 whose rank is 2 gets two gifts

Employee # 3 whose rank is 1 gets one gift

Employee # 4 whose rank is 5 gets two gifts

Employee # 5 whose rank is 2 gets one gift

Therefore, total gifts required is 1 + 2 + 1 + 2 + 1 = 7

Similarly, for testcase 2, adhering to rules mentioned above,

Employee # 1 whose rank is 1 gets one gift

Employee # 2 whose rank is 2 gets two gifts

Therefore, total gifts required is 1 + 2 = 3

Program:

#include<stdio.h>

long int arr[100010];

long int brr[100010];

int main()

{

  int test_case;

  scanf("%d",&test_case);

  for(int i = 1; i <= test_case; i++)

  {

    int n;

    long int gift = 0, temp = 0;

    scanf("%d",&n);

    for(int i = 0; i < n; i++)

    {

        scanf("%ld",&arr[i]);

    }

    brr[0] = 1;

    for(int i = 1; i < n; i++)

    {

      if(arr[i] > arr[i-1])

      {

        brr[i] = brr[i-1] + 1;

      }

      else

      {

        brr[i] = 1;

      }

    }

    gift = brr[n-1];

    for(int i = n-2; i >= 0; i--)

    {

      if(arr[i] > arr[i+1])

      {

        temp = brr[i+1] + 1;

      }

      else

        temp = 1;

      gift = gift + ((temp > brr[i]) ? temp : brr[i]);

      brr[i] = temp;

    }

    printf("%ld\n",gift);

  }

  return 0 ;

}

You can also run it on an online IDE:    

https://ide.geeksforgeeks.org/17QQxk3PW3

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!  Happy Coding !! Cheers!!!

Related Links:

https://codepiggy.blogspot.com/2021/02/prime-time-again-codevita-9-zonal-round.html

Kth largest factor of N - Code Vita 2017 | round 1

 kth largest factor of N  

Problem

A positive integer d is said to be a factor of another positive integer N if when N is divided by d, the remainder obtained is zero. For example, for the number 12, there are 6 factors 1, 2, 3, 4, 6, 12. Every positive integer k has at least two factors, 1 and the number k itself.

 Given two positive integers N and k, write a program to print the kth largest factor of N.  

Input 

The input is a comma separated list of positive integer pairs (N, k)

Output 

The kth highest factor of N. If N does not have k factors, the output should be 1.

Constraints 

1<N<10000000000. 1<k<600

You can assume that N will have no prime factors which are larger than 13.

Example 1 

Input: 12,3

Output: 4

Explanation:

N is 12, k is 3. The factors of 12 are (1,2,3,4,6,12). The highest factor is 12 and the third largest factor is 4. The output must be 4

Example 2 

Input: 30,9

Output: 1

Explanation:

 N is 30, k is 9. The factors of 30 are (1,2,3,5,6,10,15,30). There are only 8 factors. As k is more than the number of factors, the output is 1.

Program

#include <stdio.h>

int main() {

int n,k,i,c=0;

scanf("%d",&n);

scanf("%d",&k);

for(i=n;i>=1;i--)

{

    if((n%i)==0)

    c++;

    if(c==k)

    {

    printf("%d",i);

    break;

    }

}

if(c!=k)

printf("1");

return 0;

}

Output

12 3

4

You can run it in an online IDE: https://ide.geeksforgeeks.org/6xxVFQA20s

Your feedback are most welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links: The Great Chase

The Great Chase - Code Vita 2017 | round 1

The Great Chase

Problem

Welcome to the Planet Zandar, the second most prominent planet in the Milky Way Galaxy (of course after our own Earth). 

The planet  is in a distress condition, a Group of Galactic pirates, Zorons have stolen the Trident Crystal, which is the main source of energy of the planet, and are escaping the Galaxy. The Nova Corps, the military agency of Zandar, have gathered intelligence that the Zoronion space craft can run in cosmic leaps of exactly D units, (it means that the space craft will move D units from its position in every leap/turn) and is currently I units away from Zandar. 

The Zandarian Space crafts can run in cosmic leaps of exactly Z units. The Commander of Nova Corps wants to know the smallest number of leaps required to catch Zorons (Note that it is possible to catch the pirates only when they will be at the same point in the cosmic universe). The Zorons, even though are clever thieves, travel in one direction, and keep jumping exactly D units without stopping at any point. The Nova Corps can dial in the number of jumps they need to make (each of them exactly Z units), and reach the place almost instantly. They can then wait there until the Zorons arrive, and recover the Trident Crystal.

However, their wizard has told them that there may be situations where it is impossible for the Nova corps to be at the same distance as the Zorons. 

As the planet is out of power currently, their supercomputers are shut down and they are not able to calculate the required information. As you are there from Earth they have approached you for help.

Note: Assume that the Cosmic universe is one dimensional.

Input

An integer T for number of test cases, followed by T test cases each one consisting of three numbers 1) I :- initial distance of Zorons 2) D:- distance covered in a single cosmic leap by Zoronion space craft. 3) Z:- distance covered by Zandarian space crafts. 

Output  

Single number, the number of leaps required to catch the pirates, and if it is not possible to catch them, output will be -1

Constraints 

 1 ≤ I,D ≤ 1012 1≤ Z ≤ 109

Example 1

Input: 2 9 5 12 5 7 9

 

Output: 2 6

Explanation: The first line is 2, so T is 2, and there are 2 test cases.

In the first test case, The Zorons will initially be at 9 and then they will leap to 14,19 24.....  The Nova Corps can take leaps of 12 and will catch them nearest at a distance 24, taking 2 leaps 12 and 24.

In the second test case, The Zorons will initially be at 5 and then they will leap to 12,19 26, 33, 40, 47, 54.....  The Nova Corps can take leaps of 9 and will catch them nearest at 54, taking 6 leaps.

Hence the output has 2 lines, 2 and 6.

Example 2

Input: 1 10 15 20

Output: 2

Explanation: The first line is 1, so T is 1, and there is 1 test case.

The Zorons will initially be at 10, and jump in jumps of 15, landing at 25,40 

The Nova Corps take leaps of 20, and arrive at 20, 40. Hence, they can meet at 40 after 2 leaps. The output is 2.

Note:

The solution is so simple but it seems little complicated because of the condition: If it is impossible to catch return -1.

Program

#include <stdio.h>

int main() {

int i,d,z,s,l,k,c=0,j,t;

scanf("%d",&t);

for(j=0;j<t;j++)

{

scanf("%d",&i);

scanf("%d",&d);

scanf("%d",&z);

c=0;

s=1;

while(s!=0)

{

    i=i+d;

    for(k=2;k<=z;k++)

    {

        if(((i%k)==0)&&((z%k)==0))

        ++c;

    }

        if(c==0)

        {

        printf("-1 ");

        break;

        }

    

    s=i%z;

    if(s==0)

    {

        l=i/z;

        printf("%d ",l);

    }

    l=0;

}

}

return 0;

}

Output

example 1:  2 9 5 12 5 7 9

                    2 6

example 2:  1 10 15 20

                    2

example 3: 2 1 2 4 10 15 29

                    -1  -1

You can also run it on a online IDE: https://ide.geeksforgeeks.org/uwt0OABm8i

Your feedback are always welcome ! If you have and doubt you can contact or leave a comment!! Cheers!!!

Related Links: Milk man and His Bottles

                          Bride Hunting 2018

Codu And Sum Love 2018

Codu And Sum Love

Problem Description

```

Scanner sc = new Scanner(System.in);

long sum = 0;

int N = sc.nextInt();

for (int i = 0; i < N; i++) {

final long x = sc.nextLong(); // read input

String str = Long.toString((long) Math.pow(1 << 1, x));

str = str.length() > 2 ? str.substring(str.length() - 2) : str;

sum += Integer.parseInt(str);

}

System.out.println(sum%100);

```

Given N number of x’'s, perform logic equivalent of the above Java code and print the output

Constraints

 1<=N<=10^7 0<=x<=10^18

Input Format

 First line contains an integer N

Second line will contain N numbers delimited by space

Output

 Number that is the output of the given code by taking inputs as specified above

Explanation

Example 1

Input

 4 8 6 7 4

 Output

 64

Example 2

Input

3

1 2 3

Output

14

Program

#include <stdio.h>
long power(long k)
{
    long i,j=1;
    for(i=1;i<=k;i++)
        j=j*2;
        return j;
}
long length(long k)
{
    long ct=0,n1;
    while(k)
    {
        ct++;
        k=k/10;
    }
    return ct;
}
long reduce(long p1,long r1)
{
    long ct=0,k,cnt,rev=0,a[1000],h=0,i,sum1=0;
    while(p1)
    {
      k=p1%10;
      a[h]=k;
      h++;
      p1=p1/10;
     }
      for(i=1;i>=0;i--)
      sum1=sum1*10+a[i];
    return sum1;
}
int main() {
 long x,n,sum=0,r[70],p,c,f=0,i;
 scanf("%ld",&n);
 for(i=0;i<n;i++)
 {
    scanf("%ld",&x);
    p=power(x);
    c=length(p);
    if(c>2)
    {
    r[f++]=reduce(p,c);
    }
    else
    r[f++]=p;
 }
 for(i=0;i<n;i++)
 
 sum=sum+r[i];
   printf("%ld",(sum%100));
 
 
 return 0;
}

Output:

4 8 6 7 4

64

You can also try running it on online IDE: https://ide.geeksforgeeks.org/G3gXokhTbW

Your doubts and feedback are welcomed! you can comment it below Cheers!

Related Link: Super Ascii