The Constellation Problem - TCS CodeVita

Approach

As we can see in the sample example above, all the vowels are represented by a 3 * 3 grid. If you look closely, ‘A’, ‘U’, and ‘O’ have the unique 2nd column from all other vowels. Hence, we can identify them based on their second column.

Now, we are left with only ‘I’ and ‘E” which have the same 2nd column. We can compare them based on the first column. Please see the above example in which we can see that both ‘I’ and ‘E’ have different first columns.
 

Refer to the below implementation of the above approach:-

import java.util.*;
import java.io.*; 
  
public class Main {
	public static void main (String[] args) {
	    Scanner sc = new Scanner(System.in); 
		int n = sc.nextInt();
		char a[][] = new char[3][n];
		for(int i=0;i<3;i++) {
			a[i] = sc.next().toCharArray();
		}
		StringBuilder res = new StringBuilder();
		int i = 0;
		while(i<n) {
			if(a[0][i] == '#') {
				res.append("#");
				i++;
			}
			else {
				if(a[0][i+1]=='*' && a[1][i+1]=='*' && a[2][i+1]=='.') {
					res.append("A");
				}
				else if(a[0][i+1]=='.' && a[1][i+1]=='.' && a[2][i+1]=='*') {
					res.append("U");
				}
				else if(a[0][i+1]=='*' && a[1][i+1]=='.' && a[2][i+1]=='*') {
					res.append("O");
				}
				else {
					if(a[0][i]=='*' && a[1][i]=='.' && a[2][i]=='*') {
						res.append("I");
					}
					else {
						res.append("E");
					}
				}
				i += 3;
			}
		}
		System.out.println(res);
	}
}

Time Complexity: O(N)

We are simply running a while loop of O(N) time.

Space Complexity: O(1)

We are not using any auxiliary space.

Check out this article to find out everything about TCS NQT.

FAQs

Why do we use a StringBuilder in the above approach?
StringBuilder is a mutable object of String. This means that we can update them. If we use String objects (immutable objects), then updating them would take O(N) time.

What is the time and space complexity of the approach used?
The time complexity is O(N) and the space complexity is O(1).

Conclusion

In this article, we have extensively discussed the following things:

1. We first discussed the problem statement of a TCS codevita contest.
2. Then we discussed the approach and implementation to this TCS codevita problem.

Check out TCS Interview Experience to learn about TCS’s hiring process.

We hope that this blog has helped you enhance your knowledge regarding such coding problems from TCS codevita or any coding contest and if you would like to learn more, check out our articles here. You can attempt this problem here.

Do upvote our blog to help other ninjas grow. Happy Coding!