Codeforces 1512A Spy Detected! Solution & Explanation

Klook.com
Post Views: 171

Difficulty : 800

Problem Description

You are given an array a consisting of n (n≥3) positive integers. It is known that in this array, all the numbers except one are the same (for example, in the array [4,11,4,4] all numbers except one are equal to 4 ).

Print the index of the element that does not equal others. The numbers in the array are numbered from one.

Input

The first line contains a single integer t (1≤t≤100). Then t test cases follow.

The first line of each test case contains a single integer n (3≤n≤100) — the length of the array a .

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤100).

It is guaranteed that all the numbers except one in the a array are the same.

Output

For each test case, output a single integer — the index of the element that is not equal to others.

Examples

Input4
4
11 13 11 11
5
1 4 4 4 4
10
3 3 3 3 10 3 3 3 3 3
3
20 20 10
Output2
1
5
3

Solution

In our approach, we assume that the first element of the array is tmp1. Then, in the first for loop, the program traverses the array and compares each current element with tmp1 to find the second distinct value tmp2 and records its position as tmp2Idx.

In the second for loop, the program traverses the array backward, starting from the end. In each iteration, it checks whether the current element is equal to tmp1. If it is, it means the current element is not the unique number because there exists another distinct number, whose position is tmp2Idx. Therefore, the program outputs tmp2Idx + 1, which represents the position of the second distinct element. If the current element is not equal to tmp1, it means the current element is the unique number because no other number is equal to it. Thus, the program outputs 1, indicating the position of the first element.

This approach ensures finding the position of the unique number in the array and requires only two traversals of the array, making it highly efficient. The time complexity of this solution is O(n).

C# Solution

Solution1

int t = int.Parse(Console.ReadLine());

for(int i=0; i<t; i++){
    int n = int.Parse(Console.ReadLine());
    
    int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    var tmp1 = arr[0];
    var tmp2 = 0;
    
    var tmp2Idx = 0;
    
    for(int j=1; j<arr.Length; j++){
        if(arr[j]!=tmp1){
            tmp2 = arr[j];
            tmp2Idx = j;
            break;
        }
    }
    
    for(int k=arr.Length-1; k>0; k--){
        if(k!=tmp2Idx){
            if(arr[k]==tmp1){
                Console.WriteLine(tmp2Idx+1);
                break;
            }
            else{
                Console.WriteLine(1);
                break;
            }
        }
    }
    
}

Time Complexity : O(n)

Java Solution

Solution1

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int t = scanner.nextInt();
        scanner.nextLine();
        
        for(int i=0; i<t; i++){
            int n = scanner.nextInt();
            scanner.nextLine();
            
            int[] arr = Arrays.stream(scanner.nextLine().split(" "))
                       .mapToInt(Integer::parseInt)
                       .toArray();
            int tmp1 = arr[0];
            int tmp2 = 0;
            
            int tmp2Idx = 0;
            
            for(int j=1; j<arr.length; j++){
                if(arr[j]!=tmp1){
                    tmp2 = arr[j];
                    tmp2Idx = j;
                    break;
                }
            }
            
            for(int k=arr.length-1; k>0; k--){
                if(k!=tmp2Idx){
                    if(arr[k]==tmp1){
                        System.out.println(tmp2Idx+1);
                        break;
                    }
                    else{
                        System.out.println(1);
                        break;
                    }
                }
            }
            
        }
    }
}

Time Complexity : O(n)

Klook.com

Python3 Solution

Solution1

t = int(input())

for i in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    tmp1 = arr[0]
    tmp2 = 0
    tmp2Idx = 0
    
    for j in range(1,len(arr)):
        if(arr[j]!=tmp1):
            tmp2 = arr[j];
            tmp2Idx = j;
            break;
    
    for k in range(len(arr)-1, 0, -1):
        if(k!=tmp2Idx):
            if(arr[k]==tmp1):
                print(tmp2Idx+1)
                break
            else:
                print(1)
                break

Conclusion

🧡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 – 1512A – Codeforces

Random Codeforces Posts

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *