Zero Count | Code Vita 2023 | Zero Count Code Vita 2023 Solution | Code Vita 2023 season 11 solution

 Problem Description:

You are given a binary string B of length L which contains K ones and remaining zeros. You are required to place the K ones in the binary string in such a way that the longest consecutive zeros have the least length possible. Once such a binary string is constructed, you are required to print the length of the contiguous block of zeros, which has the largest length.

Constraints

0 <= K <= L

1 <= L <= 10^6

 Input

Single line consisting of two space separated integers denoting L and K.

Output

Print a single integer denoting the length of the longest consecutive zeros as per the problem. 

Time Limit (secs)

1

 Examples

 Example 1

Input

3 1

Output

1

Explanation

B is of length 3 and it has 1 one’s.

So the possible strings as per the problem are 010, 001, 100.

In the first case, the maximum length of consecutive zeros is 1 whereas in the other two cases it is 2. Hence the constructed binary string is 010 and the output is 1.

Example 2

Input

3 3

Output

0

Explanation

B is of length 3 and it has all three one’s. There is no block of zeros, hence the output is 0.


Solution in C:

#include <stdio.h>


// Function to count zeros based on values of L and K
int zerocount(int L, int K) {
// Base case: if K is 0, return L
if (K == 0) {
return L;
}
// Base case: if K is equal to L, return 0
if (K == L) {
return 0;
}
// Initialize max_zeros to 0
int max_zeros = 0;
// If K is greater than 0, set max_zeros to 1
if (K > 0) {
max_zeros = 1;
}
// Return the value of max_zeros
return max_zeros;
}


int main() {
// Declare variables L and K
int L, K;
// Input values for L and K
scanf("%d %d", &L, &K);
// Call the zerocount function and store the result in res
int res = zerocount(L, K);
// Print the result
printf("%d\n", res);


return 0;
}

You can also run it on an online IDE: 

https://ide.geeksforgeeks.org/online-c-compiler/17c95992-ebe1-4724-ae1f-ac10039b7fba

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

Related Links:

at No comments:
Labels: , ,

Dining Table Seating Arrangement Problem | Code Vita 2020 | Code Vita season 9

 Problem Description:

In a Conference ,attendees are invited for a dinner after the conference.The Co-ordinator,Sagar arranged around round tables for dinner and want to have an impactful seating experience for the attendees.Before finalizing the seating arrangement,he wants to analyze all the possible arrangements.These are R round tables and N attendees.In case where N is an exact multiple of R,the number of attendees must be exactly N//R,,If N is not an exact multiple of R, then the distribution of attendees must be as equal as possible.Please refer to the example section before for better understanding.

For example, R = 2 and N = 3

All possible seating arrangements are

(1,2) & (3)

(1,3) & (2)

(2,3) & (1)

Attendees are numbered from 1 to N.

Input Format:

The first line contains T denoting the number of test cases.

Each test case contains two space separated integers R and N, Where R denotes the number of round tables and N denotes the number of attendees.

Output Format:

Single Integer S denoting the number of possible unique arrangements.

Constraints:

0 <= R <= 10(Integer)

0 < N <= 20 (Integer)

Sample Input 1:

1

2 5

Sample Output 1:

10

Explanation:

R = 2, N = 5

(1,2,3) & (4,5)

(1,2,4) & (3,5)

(1,2,5) & (3,4)

(1,3,4) & (2,5)

(1,3,5) & (2,4)

(1,4,5) & (2,3)

(2,3,4) & (1,5)

(2,3,5) & (1,4)

(2,4,5) & (1,3)

(3,4,5) & (1,2)

Arrangements like

(1,2,3) & (4,5)

(2,1,3) & (4,5)

(2,3,1) & (4,5) etc.

But as it is a round table, all the above arrangements are same.

Solution in C:

#include <stdio.h>


// Function to calculate factorial
long long factorial(int n) {
long long result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}


int main() {
int testcases;
scanf("%d", &testcases);


for (int i = 0; i < testcases; i++) {
int tables, people;
scanf("%d %d", &tables, &people);


if (tables >= people) {
printf("1\n");
} else {
int PA = people / tables;
int PB = PA + 1;
int TB = people % tables;
int TA = tables - TB;


// Using DP to store factorials pre-hand
long long fact[people + 2];
fact[0] = 1;
for (int j = 1; j <= people + 1; j++) {
fact[j] = j * fact[j - 1];
}


// Dividing people between tables
long long divide = fact[people] / (fact[PA] * fact[TB] * fact[TA] * fact[PB]);


long long result;
if (PB >= 4) {
result = divide * (factorial(PA - 1) / 2) * (factorial(TA) / 2) * (factorial(PB - 1) / 2) * (factorial(TB) / 2);
} else {
result = divide;
}


printf("%lld\n", result);
}
}


return 0;
}


You can also run it on an online IDE: 

https://ide.geeksforgeeks.org/online-c-compiler/c5c2e7bb-031b-4805-9d5d-022c5f61b61c

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

Related Links:

at No comments:
Labels: ,

3 Palindromes | Code Vita 2020 Question and Solution | Code Vita 9

 Problem Description

In this 3 Palindrome, Given an input string word, split the string into exactly 3 palindromic substrings. Working from left to right, choose the smallest split for the first substring that still allows the remaining word to be split into 2 palindromes. Similarly, choose the smallest second palindromic substring that leaves a third palindromic substring.

If there is no way to split the word into exactly three palindromic substrings, print “Impossible” (without quotes). Every character of the string needs to be consumed.

Cases not allowed –

After finding 3 palindromes using above instructions, if any character of the original string remains unconsumed.

No character may be shared in forming 3 palindromes.

Constraints

1 <= the length of input sting <= 1000

Input

First line contains the input string consisting of characters between [a-z].

Output

Print 3 substrings one on each line.

Time Limit

1

Example 1

Input

nayannamantenet

Output

nayan

naman

tenet

Explanation

The original string can be split into 3 palindromes as mentioned in the output.

However, if the input was nayanamantenet, then the answer would be “Impossible”.


Example 2

Input

aaaaa

Output

a

a

aaa

Explanation

The other ways to split the given string into 3 palindromes are as follows –

[a, aaa, a], [aaa, a, a], [aa, aa, a], etc.

Since we want to minimize the length of the first palindromic substring using left to right processing, the correct way to split is [a, a, aaa].


Example 3

Input

aaaabaaaa

Output

a

aaabaaa

a

Explanation

The other ways to split the given string into 3 palindromes are as follows –

[aaaa, b, aaaa], [aa, aabaa, aa], etc.

Since we want to minimize the length of the first palindromic substring using left to right processing, the correct way to split is [a, aaabaaa, a].


Solution in  C:

#include <stdio.h>


#define mod 1000000007
#define MAX_LENGTH 1000


typedef long long int lld;


int isPalindrome(char str[], int start, int end) {
while (start < end) {
if (str[start] != str[end]) {
return 0; // Not a palindrome
}
start++;
end--;
}
return 1; // Palindrome
}


int main() {
char s[MAX_LENGTH], s1[MAX_LENGTH], s2[MAX_LENGTH], s3[MAX_LENGTH];
scanf("%s", s);


int l = 0;
while (s[l] != '\0') {
l++;
}


for (int i = 1; i < l - 1; i++) {
for (int k = 0; k < i; k++) {
s1[k] = s[k];
}
s1[i] = '\0';


if (isPalindrome(s, 0, i - 1)) {
for (int j = 1; j < l - i; j++) {
for (int k = 0; k < j; k++) {
s2[k] = s[i + k];
}
s2[j] = '\0';


for (int k = 0; k < l - i - j; k++) {
s3[k] = s[i + j + k];
}
s3[l - i - j] = '\0';


if (isPalindrome(s2, 0, j - 1) && isPalindrome(s3, 0, l - i - j - 1)) {
printf("%s\n%s\n%s\n", s1, s2, s3);
return 0;
}
}
}
}


printf("Impossible\n");
return 0;
}



You can also run it on an online IDE: 

https://ide.geeksforgeeks.org/online-python3-compiler/294545fa-8a51-46da-ab50-8fb862187677

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

Related Links:



at No comments:
Labels: , ,

Television Set | Code Vita 2020 | Code Vita 9

 Television Set 

Problem Description

Dr. Vishnu is opening a new world class hospital in a small town designed to be the first preference of the patients in the city. Hospital has N rooms of two types – with TV and without TV, with daily rates of R1 and R2 respectively.

However, from his experience Dr. Vishnu knows that the number of patients is not constant throughout the year, instead it follows a pattern. The number of patients on any given day of the year is given by the following formula – (6-M)^2 + |D-15| , where M is the number of month (1 for jan, 2 for feb …12 for dec) and D is the date (1,2…31). All patients prefer without TV rooms as they are cheaper, but will opt for with TV rooms only if without TV rooms are not available. Hospital has a revenue target for the first year of operation. Given this target and the values of N, R1 and R2 you need to identify the number of TVs the hospital should buy so that it meets the revenue target. Assume the Hospital opens on 1st Jan and year is a non-leap year. Constraints Hospital opens on 1st Jan in an ordinary year 5 <= Number of rooms <= 100 500 <= Room Rates <= 5000 0 <= Target revenue < 90000000
Input Format First line provides an integer N that denotes the number of rooms in the hospital Second line provides two space-delimited integers that denote the rates of rooms with TV (R1) and without TV (R2) respectively Third line provides the revenue target
Output Minimum number of TVs the hospital needs to buy to meet its revenue target. If it cannot achieve its target, print the total number of rooms in the hospital. Test Case Example-1 : Input 20 1500 1000 7000000 Output 14 Explanation Using the formula, the number of patients on 1st Jan will be 39, on 2nd Jan will be 38 and so on. Considering there are only twenty rooms and rates of both type of rooms are 1500 and 1000 respectively, we will need 14 TV sets to get revenue of 7119500. With 13 TV sets Total revenue will be less than 7000000 Example-2 : Input 10 1000 1500 10000000 Output 10 Explanation

In the above example, the target will not be achieved, even by equipping all the rooms with TV. Hence, the answer is 10 i.e. total number of rooms in the hospital.

Solution in C:
#include <stdio.h>


#define mod 1000000007
#define MAX_LENGTH 1000


typedef long long int lld;


int isPalindrome(char str[], int start, int end) {
while (start < end) {
if (str[start] != str[end]) {
return 0; // Not a palindrome
}
start++;
end--;
}
return 1; // Palindrome
}


int main() {
char s[MAX_LENGTH], s1[MAX_LENGTH], s2[MAX_LENGTH], s3[MAX_LENGTH];
scanf("%s", s);


int l = 0;
while (s[l] != '\0') {
l++;
}


for (int i = 1; i < l - 1; i++) {
for (int k = 0; k < i; k++) {
s1[k] = s[k];
}
s1[i] = '\0';


if (isPalindrome(s, 0, i - 1)) {
for (int j = 1; j < l - i; j++) {
for (int k = 0; k < j; k++) {
s2[k] = s[i + k];
}
s2[j] = '\0';


for (int k = 0; k < l - i - j; k++) {
s3[k] = s[i + j + k];
}
s3[l - i - j] = '\0';


if (isPalindrome(s2, 0, j - 1) && isPalindrome(s3, 0, l - i - j - 1)) {
printf("%s\n%s\n%s\n", s1, s2, s3);
return 0;
}
}
}
}


printf("Impossible\n");
return 0;
}




You can also run it on an online IDE: 


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


at No comments:
Labels: , ,

Minimize the sum problem | Code Vita 2020 | Code Vita 9


Problem Description:

Given an array of integers, perform atmost K operations so that the sum of elements of final array is minimum. An operation is defined as follows – Consider any 1 element from the array, arr[i]. Replace arr[i] by floor(arr[i]/2). Perform next operations on the updated array. The task is to minimize the sum after utmost K operations.

Constraints 1 <= N K <= 10^5.
Input First line contains two integers N and K representing size of array and maximum numbers of operations that can be performed on the array respectively. Second line contains N space separated integers denoting the elements of the array, arr.
Output

Print a single integer denoting the minimum sum of the final array. 

Input

4 3

20 7 5 4


Output

17


Explanation

Operation 1 -> Select 20. Replace it by 10. New array = [10, 7, 5, 4]

Operation 2 -> Select 10. Replace it by 5. New array = [5, 7, 5, 4].

Operation 3 -> Select 7. Replace it by 3. New array = [5,3,5,4].

Sum = 17.


Solution in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position */
        while (j >= 0 && arr[j] < key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int minimizeSum(int N, int K, int arr[]) {
    int i;
    // Sort the array in descending order
    insertionSort(arr, N);

    for (i = 0; i < K; i++) {
        // Perform the operation on the maximum element
        arr[0] = arr[0] / 2;
        // Re-sort the array
        insertionSort(arr, N);
    }

    int sum = 0;
    for (i = 0; i < N; i++) {
        sum += arr[i];
    }

    return sum;
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);

    int arr[N];
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    int result = minimizeSum(N, K, arr);
    printf("%d\n", result);

    return 0;
}


You can also run it on an online IDE: 


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/2024/01/restaurants-code-vita-8-round-2.html


at No comments:
Labels: , , ,

Restaurants - Code Vita 8 | Round 2

Restaurants

Problem Description:

Looking for a place to rent in New York, Codu wants to stay in a place close to as many restaurants as possible and walk as little as possible to reach them. As he is a vegetarian, and likes only some types of food, there are only a few restaurants that meet his criteria.

For convenience he models the roads as rectangular grid roads and plots the restaurant locations at the intersection of two roads there. To simplify further, he approximates the distance as the number of blocks between two places. Given the maximum distance he wants to walk, he wants to find the most optimal location(from which he can reach the maximum number of restaurants within that distance).

The grid starts at (0,0) at the southwest corner, and goes to (N,0) at the south east corner, and to (N,M) at the north east corner. If two locations the same (maximum)number of restaurants he can walk to, he would prefer to have the southern most location (lowest Y coordinate). If two locations lie on the same southernmost road and have the same (maximum) number of restaurants he can walk to, he would prefer the westernmost location (lowest X coordinate).

Constraints
1 < N,M,K <= 1000
House can’t be in the same block where there exists a restaurant
Input Format
First line contains two integers N, M the number of horizontal and vertical blocks(intervals between roads). The grid is given the coordinates starting with (0,0) on thelower left corner and (N,M) the upper right corner. The next line contains K, the number of restaurants. The next K pairs of integers give the coordinates of the K restaurants. The next line gives the distance he wants to walk (in blocks)
Output
Three integers, first two giving the coordinates of the optimal location and the next integer giving the number of restaurants reachable from that location.

Test Case

Example 1:

Input

4 4
5
1 1
1 2
3 3
4 4
2 4
4

Output

3 1 5

Solution:

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

struct Restaurant {
    int x, y;
};

int distance(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

int main() {
    int N, M, K;
    scanf("%d %d", &N, &M);
    
    scanf("%d", &K);
    struct Restaurant restaurants[K];
    for (int i = 0; i < K; i++) {
        scanf("%d %d", &restaurants[i].x, &restaurants[i].y);
    }
    
    int maxDistance;
    scanf("%d", &maxDistance);
    
    int maxRestaurants = 0;
    int optimalX, optimalY;

    for (int x = 0; x <= N; x++) {
        for (int y = 0; y <= M; y++) {
            int currentRestaurants = 0;
            
            for (int i = 0; i < K; i++) {
                if (distance(x, y, restaurants[i].x, restaurants[i].y) <= maxDistance) {
                    currentRestaurants++;
                }
            }

            if (currentRestaurants > maxRestaurants || 
                (currentRestaurants == maxRestaurants && (y < optimalY
|| (y == optimalY && x < optimalX)))) {
                maxRestaurants = currentRestaurants;
                optimalX = x;
                optimalY = y;
            }
        }
    }

    printf("%d %d %d\n", optimalX, optimalY, maxRestaurants);

    return 0;
}


You can also run it on an online IDE:  


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

at No comments:
Labels: , ,
Subscribe to: Posts (Atom)

Super Market Problem | TCS Code Vita 2023 - Zone 1 | Super Market TCS Code Vita 2023 Solution | Code Vita 2023 | Code Vita 2023 season 11 solution

 Problem Description: In a Super market we will find many variations of the same product. In the same way we can find many types of rice bag...