Codeforces 59B Fortune Telling Solution & Explanation

Difficulty : 1200

Problem Description

Marina loves Sasha. But she keeps wondering whether Sasha loves her. Of course, the best way to know it is fortune telling. There are many ways of telling fortune, but Marina has picked the easiest one. She takes in her hand one or several camomiles and tears off the petals one by one. After each petal she pronounces alternatively “Loves” and “Doesn’t love”, at that Marina always starts with “Loves”. There are n camomiles growing in the field, possessing the numbers of petals equal to a₁, a₂, … a_n. Marina wants to pick a bouquet with the maximal possible total number of petals so that the result would still be “Loves”. Help her do that; find the maximal number of petals possible in the bouquet.

Input

The first line contains an integer n (1 ≤ n ≤ 100), which is the number of flowers growing in the field. The second line contains n integers a_i (1 ≤ a_i ≤ 100) which represent the number of petals on a given i-th camomile.

Output

Print a single number which is the maximal number of petals in the bouquet, the fortune telling on which would result in “Loves”. If there are no such bouquet, print 0 instead. The bouquet may consist of a single flower.

Examples

Understand this problem in 3 seconds

Given an array, you need to select some of its elements to form the largest possible odd number sum. If such a sum exists, return that sum; otherwise, return 0.

Solution

We need to consider the following:

• The nature of odd numbers: the sum of two odd numbers is even, the sum of an odd number and an even number is odd, and the sum of two even numbers is even.

Therefore, if there exists at least one odd number in the array, the answer cannot be 0.

Additionally, if there is at least one odd number present, all even numbers can be included in the sum without affecting the oddness of the result (since odd + even = odd).

However, if the number of odd numbers is a multiple of 2 (i.e., even), this means that the sum of these odd numbers will be even. In this case, we should exclude the smallest odd number from the sum to ensure that the remaining sum is odd again.

C# Solution

Solution1

int n = int.Parse(Console.ReadLine());
int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

int odd_Cnt = 0;
int res = 0;
int min_Odd = 101;

foreach(var item in arr){
    if(item%2==1){
        odd_Cnt+=1;
        if(item<min_Odd){
            min_Odd = item;
        }    
    }
    res+= item;
}

if(odd_Cnt==0){
    Console.WriteLine(0);
}
else{
    if(odd_Cnt%2==0){
        Console.WriteLine(res-min_Odd);
    }
    else{
        Console.WriteLine(res);
    }
}

Time Complexity : O(n)

Java Solution

Solution1

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
        int[] arr = Arrays.stream(scanner.nextLine().split(" "))
                          .mapToInt(Integer::parseInt)
                          .toArray();
                          
        int odd_Cnt = 0;
        int res = 0;
        int min_Odd = 101;
        
        for(int item : arr){
            if(item%2==1){
                odd_Cnt+=1;
                if(item<min_Odd){
                    min_Odd = item;
                }    
            }
            res+= item;
        }
        
        if(odd_Cnt==0){
            System.out.println(0);
        }
        else{
            if(odd_Cnt%2==0){
                System.out.println(res-min_Odd);
            }
            else{
                System.out.println(res);
            }
        }

    }
}

Conclusion

This is the second problem from codeforces contest – Dashboard – Codeforces Beta Round 55 (Div. 2) – Codeforces

You can find the solution for the first problem here – Codeforces 59A Word Solution & Explanation

🧡If my solution helps, that is my honor!

🧡You can support me by sharing my posts, thanks you~~

✅If you got any problem about the explanation or you need other programming language solution, please feel free to let me know !!

The problem link : Problem – 59B – Codeforces

Some Random Codeforces Posts