• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Check if an array has duplicate numbers in O(n) time and O(1) space

January 8, 2015 by Dhaval Dave

We have array  a[ ]= {1, 2, 3, 4, 5, 6, 7, 8, 4, 10};
And we need to find a number which is duplicate in O(n) and Space complexity O(1)

Method 1 ) Sorting
Sort it and u’ll get array = 1, 2, 3, 4, 4, 5, 6, 7, 8, 10 and find repeating element such that its index are different, but sorting takes O(nlogn)

Method 2) Hashing.

Keep Hashmap with <key, count> pair
Hashmap will contain
1,1
2,1
3,1
4,2
and return 4.
But it will take O(n) space Complexity

Method 3) Changing Array

Check if A [ abs(A[i]) ] is positive, then make it negative,
if its already negative then we found number.
( This trick will work only if all numbers are positive )

say array is 1, 2, 3, 4, 5, 6, 7, 8, 4, 10

so
while processing 1, w’ll make A[1] = -A[1], so 2 will become -2.
while processing 2, w’ll make A[2] = -A[2], so 3 will become -3.
while processing 3, w’ll make A[3] = -A[3], so 4 will become -4.
while processing 4, w’ll make A[4] = -A[4], so 5 will become -5.
while processing 5, w’ll make A[5] = -A[5], so 6 will become -6.
.
.
.
while processing 4, we checked that A[4] is already negative, So this is duplicate number.

-In order to get Original Array, we can make all sign as positive after wards
(Write/Append this code in ur code)


Working Code http://ideone.com/Y9eStG

#include <iostream>
using namespace std;

int main() {
int a[]= {1,2,3,4,5,6,7,8,4,10};
for(int i=0;i<sizeof(a)/sizeof(*a);i++){
if ( a[abs(a[i])]>0 ){
a[abs(a[i])]=-(a[abs(a[i])]);
}
else if (a[abs(a[i])]<0){
cout<<abs(a[i])<<endl;
}

}
for(int i=0;i<sizeof(a)/sizeof(*a);i++){
cout << a[i] <<endl;
}
return 0;
}

Duplicate
4

Array 
1
-2
-3
-4
-5
-6
-7
-8
-4
10

Similar Articles

Filed Under: Adobe Interview Questions, Interview Questions, problem Tagged With: Array

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Find Pythagorean Triplets in an array in O(N)

Spanning Tree

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Binary Tree Isomorphic to each other

Python Dictionaries

The Magic HackerEarth Nirvana solutions Hiring Challenge

Test Cases for Round Function

CodeChef Code SGARDEN

Cisco Hiring Event 21st – 22nd Feb 2015

C++ OOPs Part1

Practo Hiring Experience

C++ OOPs Part2

SAP Off Campus Hiring_ March 2015 Sample Questions

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Count number of ways to reach a given score in a game

Print all nodes that are at distance k from a leaf node

Code Chef PRGIFT Solution

Python Array String

Find next greater number with same set of digits

Password Predictor

LeetCode : Word Search

Find two non repeating elements in an array of repeating elements

Facebook Interview Question : Interleave List

Find position of the only set bit

Difference between a LinkedList and a Binary Search Tree BST

Generic Object Oriented Stack with Template

Interfaces in C++ (Abstract Classes in C++)

Knight Tour Problem (Graph – Breadth First Search)

Given a string, find the first character which is non-repetitive

SAP Off Campus Hiring_ March 2015 Verbal Skills

Copyright © 2025 · Genesis Framework · WordPress · Log in