Code delivering the wrong result at higher inputs

Question

I am an aspiring coder. I have been trying to solve this question on codechef. What do you reckon is the problem here? A link to the question: https://www.codechef.com/submit/EVENTUAL?tab=statement My code fail when the input is 990, which, in the question refers to the value of n. The value of 'n' refers to the length of the string. My code for the question has been provided below.

import java.util.Scanner;

public class eventual_reduction {
public static void main(String[] args) {
    try (Scanner in = new Scanner(System.in)) {
        int t = in.nextInt();
        while(t-->0){
            long count =0;
            long n = in.nextInt();
            String str = in.next();
            if(n%2!=0){
                System.out.println("NO");
            }else{
                String s = str;
                for(int i=0; i<n; i++){
                    if(s.charAt(0)==str.charAt(i)){
                        count++;
                        if((count+1)%2==0){
                            for(int j=1; j<n;j++){
                                if(s.charAt(j)==str.charAt(i)){
                                    count++;
                                }
                            }
                        }
                    }
                }
                if(count%2==0){
                    System.out.println("YES");
                }else{
                    System.out.println("NO");
                }
            }
        }
    }
}

}

Could you please help me out with the code? Would love to see ways to improve my code. Thank you!

What is the concise problem? What behaviour do you get, what do you expect instead? — Queeg, Oct 19 '22 at 05:18

Abra · Accepted Answer · 2022-10-19T08:09:49.370

Basically, you need to get the frequencies of all the letters in the string. If at least one of those frequencies is odd, you print NO, otherwise you print YES.

Let's analyze your code.

String str = in.next();

I think this is more appropriate:

String str = in.nextLine();

After calling nextInt and before calling nextLine, you need to add an extra call to nextLine

long n = in.nextInt();
in.nextLine();
String str = in.nextLine();

Refer to Scanner is skipping nextLine() after using next() or nextFoo()?

It seems like you want to iterate through each letter of str and for each letter, you iterate str again and count how many times it appears.

for(int i=0; i<n; i++){
    if(s.charAt(0)==str.charAt(i)){

I don't understand the if. You are comparing every letter in str with the first letter in str. You simply need a nested for loop.

try (Scanner in = new Scanner(System.in)) {
    int t = in.nextInt();
    while (t-- > 0) {
        long count = 0;
        long n = in.nextInt();
        in.nextLine();
        String str = in.nextLine();
        if (n % 2 != 0) {
            System.out.println("NO");
        }
        else {
            String s = str;
            for (int i = 0; i < n; i++) {
                count = 1;
                for (int j = 0; j < n; j++) {
                    if (i != j) {
                        if (s.charAt(j) == str.charAt(i)) {
                            count++;
                        }
                    }
                }
                if (count % 2 == 1) {
                    System.out.println("NO");
                    count = 0;
                    break;
                }
            }
            if (count > 0) {
                if (count % 2 == 0) {
                    System.out.println("YES");
                }
                else {
                    System.out.println("NO");
                }
            }
        }
    }
}

Basicaly, in the nested for loops, we are comparing a given character, in str, with every other character in str and we repeat this for every character in str. Thus we count how many times each character appears in str. After obtaining the count, we check to see whether that count is odd. If it is then we print NO. After we have counted the occurrences of all the characters in str, we check whether we already printed NO. If we have not, then we check the final value of count to see whether it is even or odd and print YES or NO, respectively.

Alternatively, here is a solution that uses streams.

import java.util.Scanner;
import java.util.function.Function;
import java.util.stream.Collectors;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            in.nextLine();
            String str = in.nextLine();
            if (n % 2 != 0) {
                System.out.println("NO");
            }
            else {
                str.chars()
                   .boxed()
                   .collect(Collectors.groupingBy(Function.identity(),
                                                  Collectors.counting()))
                   .values()
                   .stream()
                   .filter(v -> v % 2 == 1)
                   .findFirst()
                   .ifPresentOrElse(v -> System.out.println("NO"),
                                    () -> System.out.println("YES"));
            }
        }
    }
}

The characters in the string are converted to a stream of ints.
The stream of ints is converted to a stream of Integer objects.
A frequency map is created where the map key is [essentially] a letter and the map value is the number of occurrences of that letter in the string.
The map values, i.e. the letter frequencies, are searched for one that is odd.
If an odd frequency is found, NO is printed and if no odd frequencies are found, YES is printed.

The solution passed all the tests on CodeChef.

Code delivering the wrong result at higher inputs

1 Answers1