#include <bits/stdc++.h>
int FakeCoin(vector<int> &sum){
if (sum[0] == 0) return 0;
for (int i = 1; i < sum.size(); i++) {
if (sum[i] == 0) return i;
else if (sum[i-1] == sum[i]) return i;
}
return -1;
}
Problem
Submissions
Hints & solutions
Discuss
Day 28 : Fake Coin Problem
Easy
0/40
Contributed by
3 upvotes
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.
Detailed explanation ( Input/output format, Notes, Images )
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'.
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
Sample Input 1:
2
4
1 2 2 3
5
1 2 3 4 4
Sample Output 1:
2
4
Explanation of sample output 1:
For Test 1:
‘sum’ = {1, 2, 2, 3}
‘C’ = {1, 1, 0, 1}
Index of the fake coin is 2.
For Test 2:
‘sum' = {1, 2, 3, 4, 4}
‘C’ = {1, 1, 1, 1, 0}
Index of the fake coin is 4.
Sample Input 2:
3
3
1 2 2
3
1 1 2
3
0 1 2
Sample Output 2:
2
1
0
Hint
Hint 1
Hint 2
What will be the difference between adjacent elements in sum, if there’s a fake coin present?
Approaches (2)
Approach 1
Approach 2
Linear Search 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
- if(sum[i] == sum[i-1])
- return 0
Time Complexity
O(N), where ‘N’ is the number of elements in the array ‘sum’.
We are iterating via ‘i’ from 0 to ‘N-1’, hence the overall time complexity of this solution is O(N).
Space Complexity
O(1)
We are not utilising any extra space. Thus the space complexity is constant.
Code Solution
(100% EXP penalty)
Day 28 : Fake Coin Problem
All tags
Sort by
Interview problems
C++ Solution || All test case passed || Time Complexity: O(n)
9 views
0 replies
0 upvotes
Interview problems
Python solution
def FakeCoin(s : List[int]) -> int:
for index, ele in enumerate(s):
if s[index-1] == s[index] :
return index
return 0
3 views
0 replies
0 upvotes
Interview problems
FAKE COIN XOR METHOD
public class Solution {
public static int FakeCoin(int []sum){
// Write your code here.
int ans = 0;
for (int i = 0; i < sum.length; i++) {
ans ^= sum[i];
}
for (int i = 0; i < sum.length; i++) {
ans ^= i;
}
return ans ;
}
} 101 views
0 replies
0 upvotes
Interview problems
JAVA | Easy to Understand | One Loop
public static int FakeCoin(int []sum){
// Write your code here.
for(int i=1; i<sum.length; i++){
if(sum[i]-1 != sum[i-1]){
return i;
}
}
return 0;
}
41 views
0 replies
0 upvotes
Interview problems
Rapid C++
int FakeCoin(vector<int> &sum){
// Write your code here.
for(int i=1;i<sum.size();i++){
if(sum[i]- sum[i-1]!=1)
return i;
}
}
76 views
0 replies
0 upvotes
Interview problems
Solution using Java
public class Solution {
public static int FakeCoin(int []sum){
// Write your code here.
int fake=0;
for(int i=1;i<sum.length;i++)
{
if(sum[i]==sum[i-1])
{
fake=sum[i];
}
}
return fake;
}
}
54 views
0 replies
1 upvote
Interview problems
Easy c++ solution
int FakeCoin(vector<int> &sum){
// Write your code here.
for(int i=1;i<sum.size();i++){
if(sum[i]- sum[i-1]!=1)
return i;
}
}
94 views
0 replies
0 upvotes
Interview problems
easy C++ solution
int FakeCoin(vector<int> &sum){ for(int i = 0; i<sum.size();i++){ if(sum[i] == sum[i+1]) return sum[i+1]; } }
50 views
0 replies
0 upvotes
C++ (g++ 5.4)
Console