Last Updated: 24 Dec, 2022

Day 28 : Fake Coin Problem

Easy

Problem statement

You are given an array ‘sum’ which is the prefix sum of an array of coins ‘C’ where ‘C[i]’ is ‘1’ if the coin is real, or ‘0’ if the coin is fake. There is exactly one fake coin in the array.

Return the index of the fake coin. Assume the array to be 0-indexed.

For Example:

‘sum’ = {1,1,2,3} 
Index of the fake coin is 1. 
For the given ‘sum’, ‘C’ will be {1, 0, 1, 1}. Thus the index of the fake coin is 1.

Input format:

The first line contains an integer ‘T’, denoting the number of test cases.
For each test case:
The first line contains an integer ‘N’, representing the size of the array ‘sum’.
The second line contains ‘N’ integers, denoting the elements of the array 'sum'.

Output Format:

For each testcase, return the index of the fake coin.

Constraints:

1 <=  ‘T’ <= 10^5
2 <= ‘N’ <= 10^5
0 <= ‘C[i]’ <= 1
0 <= ‘sum[i]’ <= ‘N-1’
Sum of ‘N’ for all testcases <= 10^5
There is exactly one ‘0’ in ‘C’.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

Approach:

We can simply iterate through all the elements and check for the difference between the current index and the previous index. If there’s a fake coin the difference will be 0. If the first element of ‘sum’ is 0 then the fake coin is at index 0.

Algorithm:

for ‘i’ from 1 to ‘N-1’:
- if(sum[i] == sum[i-1])
  - return i
return 0

Solve now

02 Approach

Approach:

If the fake coin is present in range [l,r], then ‘sum[r] - sum[l-1] < r-l+1’. We can use this fact to binary search over the array ‘sum’. Let ‘m = (r+l)/2 ‘.If ‘sum[m+1] == sum[m]’ the fake coin is at index ‘m+1’ . If ‘sum[r] - sum[m] < r-m’, we binary search in range [m+1,r], otherwise we binary search in range [l,m].

Algorithm:

Initialise ‘l’ = 0, ‘r’ = ‘N-1’
while(l < r)
- m = (l+r) / 2
- if(sum[m+1] == sum[m])
  - r= m+1
  - break
- if(sum[r] - sum[m] < r-m)
  - l = m + 1
- else
  - r = m
return r

Solve now