Ninja And His Old Friends

Easy
0/40
Average time to solve is 15m
14 upvotes
Asked in company
Flipkart limited

Problem statement

Ninja wants to meet his ‘N’ old friends standing in a row. All the friends along with Ninja are very happy because they are meeting after a long time. The happiness of each friend can be represented as a positive integer. Initially, Ninja has some happiness value ‘K’. Ninja shakes hands with all of his ‘N’ friends standing in a row one by one.

While shaking hands if the happiness value of Ninja matches with that of his friend, then the happiness value of Ninja becomes double. Ninja wants to calculate his happiness value after he shakes hands with all of his friends.

For Example: For ‘FRIENDS’ = [3, 2, 1, 4]. And ‘K’ = 2, following are the results after each hand shake:

1. At index 0 the happiness value of his friend is 3 and the happiness value of Ninja is 2. Both are unequal so ‘K’ remains the same.
2. At index 1 the happiness value of his friend is 2 and the happiness value of Ninja is 2. Both are equal so ‘K’ becomes 4.
3. At index 2 the happiness value of his friend is 1 and the happiness value of Ninja is 4. Both are unequal so ‘K’ remains the same.
4. At index 3 the happiness value of his friend is 4 and the happiness value of Ninja is 4. Both are equal so ‘K’ becomes 8.

As Ninja is busy with his friends so he needs your help. Can you help Ninja to find his final happiness value after all the handshakes?

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two integers ‘N' and ‘K’ denoting the number of friends and the initial happiness value ofNinja respectively.

The second line of each test case contains 'N' single space-separated integers, denoting the happiness value of each friend.
Output Format: 
For each test case, print an integer denoting the final happiness value of Ninja after all the handshakes.

The output of each test case will be printed in a separate line.

Note:

You are not required to print the expected output, and it has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 100
1 <= N <= 10 ^ 4
1 <= K <= 10 ^ 3
1 <= FRIENDS[i] <= 10 ^ 6

Where 'FRIENDS[i]' denotes the happiness value of the friend at the ‘i’th index, respectively.

Time Limit: 1 sec
Sample Input 1:
2
3 1
1 2 4 
2 4 
1 2
Sample Output 1:
8
4
Explanation of Sample Input 1:
For the first test case:
1. At index 0 the happiness value of his friend is 1 and the happiness value of Ninja is 1. Both are equal so ‘K’ becomes 2.
2. At index 1 the happiness value of his friend is 2 and the happiness value of Ninja is 2. Both are equal so ‘K’ becomes 4.
3. At index 2 the happiness value of his friend is 4 and the happiness value of Ninja is 4. Both are equal so ‘K’ becomes 8.

For the second test case:
1. At index 0 the happiness value of his friend is 1 and the happiness value of Ninja is 4. Both are unequal so ‘K’ remains the same. 
2. At index 1 the happiness value of his friend is 2 and the happiness value of Ninja is 4. Both are unequal so ‘K’ remains the same.
Sample Input 2:
2
2 5
5 5 
3 8
2 4 8
Sample Output 2:
10
16
Explanation of Sample Input 2:
For the first test case:
1. At index 0 the happiness value of his friend is 5 and the happiness value of Ninja is 5. Both are equal so ‘K’ becomes 10.
2. At index 1 the happiness value of his friend is 5 and the happiness value of Ninja is 10. Both are unequal so ‘K’ remains the same.    

For the second test case:
1. At index 0 the happiness value of his friend is 2 and the happiness value of Ninja is 8. Both are unequal so ‘K’ remains the same.
2. At index 1 the happiness value of his friend is 4 and the happiness value of Ninja is 8. Both are unequal so ‘K’ remains the same.
3. At index 2 the happiness value of his friend is 8 and the happiness value of Ninja is 8. Both are equal so ‘K’ becomes 16.
Hint

Try to use the brute force approach in this problem

Approaches (1)
Brute Force

The idea behind this approach is to simply iterate the list/array ‘FRIENDS’ and compare the happiness value of  Ninja with that of his friend. If both are the same then double the happiness value of  Ninja and repeat the same for the rest of the friends.  

 

Here is the complete algorithm:

  • Iterate the list/array ‘FRIENDS’ and for each friend at index ‘i’ do the following:
    • If ‘FRIENDS[i]’ = ‘K’ then double the ‘K’. i.e. 2 * ’K’.
  • Finally, return ‘K’.
Time Complexity

O(N), where ‘N’ is the number of friends in the list/array ’FRIENDS’.

 

As we are iterating exactly one time over an array/list of length ‘N’ so the overall time complexity is O(N).

Space Complexity

O(1).

 

As we are not using any extra space so the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Ninja And His Old Friends
Full screen
Console