Remember me
to get activation email.
There are numbers from 1 to N in an array. out of these, one of the number gets duplicated and one is missing. The task is to find out the duplicate number. Conditions: you have to do it in O(n) time without using any auxilary space (array, bitsets, maps etc..).
Dec 13th, 2006
Editorial / Best Answer
Answered by:
David Rachutin
use the following method:mark the missing number as M and the duplicated as D1) compute the sum of regular list of numbers from 1 to N call it RegularSum2) compute the sum of your array (the one with M and D) call it MySumnow you know that MySum-M+D=RegularSumthis is one equation.the second one uses multiplication:3) compute the multiplication of numbers of regular list of numbers from 1 to N call it RegularMultiplication4) compute the multiplication of numbers of your list& (the one with M and D) call it MyMultiplicationnow you know that MyMultiplication=RegularMultiplication*D/Mat this point you have two equations with two parameters, solve and rule!
Showing Answers 1 - 68 of 68 Answers
#include&stdio.h&
#include&stdlib.h&
main()
&int i, n ,j ,k ;
&int *input ;
&(&enter the size of the array
&scanf(&%d&,&n);
&input = (int *) malloc(sizeof(int)*(n+1));
&for(i = 1; i&= n ; i++) // values stored in 1 to n for convinience !!!!
& & & & (&Enter the value .... should be between 1 and %d
& , n );
& & & & scanf(&%d&,&input[i]);
&for( i =1 ; i&=n ;i++ )
& &if( input[input[i]] & 0 )
& & & & ( &%d value has been repeated...&,input[i]);
& & & & input[input[i]]= -input[input[i]];
for( i = 1 ; i&= n ; i++)
&if(input[i]&0)
& & & & (&%d value has been missing &, i);
square = 0
for each element in array
& & sum+=element
& & square+=(element)^2
p-m = n(n+1)/2 - sum & ...............(1)
p^2-m^2 = n(n+1)(2n+1)/6 -square
=& (p+m)(p-m) = n(n+1)(2n+1)/6 - square ..............(2)
Divide (2) by (1), we get the value of
p + m = [n(n+1)(2n+1)/6-square)]/[n(n+1)/2 - sum]........(3)
&solve (1) and (3) for values of p and m.
int iCurrent = 0;
for (int (i=0 ; i&N ;)
& & int currNum = arr[i];
& & if (currNum == 0)
& & {
& & & & // i has already been found and thus set to 0
& & & & ++i;
& & & & continue;
& & }
& & if (arr[CurrNum-1] == 0)
& & {
& & & & return currNum;
& & }
& & arr[i] = arr[currNum-1];
& & arr[CurrNum-1] = 0;
& & & & /// &summary&
& & & & /// Finds the first/lowest duplicate and missing element in O(n) time
& & & & /// Worst case scenario works in O(2n) but since constants are excluded from the O notation, it can be considered as O(n)
& & & & /// &/summary&
& & & & /// &param name=&A&&Array of values 1 to N where N is the size of array&/param&
& & & & void FindDuplicate(int[] A)
& & & & {
& & & & & & int N = A.Length;
& & & & & &
& & & & & & int duplicate = 0;
& & & & & & int missing = 0;
& & & & & & //Sort the array, appears as larger than O(n) but in practice is indeed O(n) and most of the time less than O(n)
& & & & & & for (int i = 0; i & N; i++)
& & & & & & {
& & & & & & & & //while the number on the position is not correct and the numbers to swap are different then swap
& & & & & & & & while (A[i] != i + 1 && A[A[i] - 1] != A[i])
& & & & & & & & & & Swap(ref A[A[i] - 1], ref A[i]);
& & & & & & & & //if the position i remains with a non-corresponding number and the numbers to swap
& & & & & & & & //are the same then we have found our duplicate and missing elements
& & & & & & & & if (A[i] != i + 1 && A[A[i] - 1] == A[i])
& & & & & & & & {
& & & & & & & & & & duplicate = A[i];
& & & & & & & & & & missing = i + 1;
& & & & & & & & & & break;
& & & & & & & & }
& & & & & & }
& & & & & & //Display the result
& & & & & & if (missing == 0)
& & & & & & & & Console.WriteLine(&No Duplicate found&);
& & & & & & else
& & & & & & {
& & & & & & & & Console.WriteLine(&Duplicate: & + duplicate);
& & & & & & & & Console.WriteLine(&Missing: & + missing);
& & & & & & }
& & & & }
& & & & /// &summary&
& & & & /// Swaps 2 values by reference without using an aux variable
& & & & /// &/summary&
& & & & /// &param name=&a&&&/param&
& & & & /// &param name=&b&&&/param&
& & & & private void Swap(ref int a, ref int b)
& & & & {
& & & & & & a ^= b; b ^= a; a ^= b;
& & & & }
Do while I & N - 1
If num-array(I) - num-array(i+1) = 0
&duplicate number is & num-array(I)
& I = N + 1
& I = I + 1
for (int i=0 ; i&n ; i++)
& swap(a[i],a[a[i]-1]
//since 1 is stored at 0th position
Give your answer:
If you think the above answer is not correct, Please select a reason and add your answer below.
- Reason -
Answer is wrong
Spelling Mistakes
Duplicate Answer
Inappropriate Answer
Answer Question
Click here to
your free account
Insert Code:
Related Answered Questions
Related Open Questions
Subscribe To RSS Feed
Random Questions
&&Asked by: &&Asked by: asuh&&Asked by: How to display nth lowest record in a table for example? How to display 4th lowest (salary) record from customer table?&&Asked by: &&Asked by: Ravindra
Interview Questions PDF Files
Interview & Career Tips
Get invaluable Interview and Career Tips delivered directly to your inbox. Get your news alert set up today, Once you confirm your Email subscription, you will be able to download Job Inteview Questions Ebook . Please contact me if you there is any issue with the download.
Latest NewsUtility functions in KnockoutJS - Knock Me Out
Thoughts, ideas, and discussion about Knockout.js
Utility Functions in KnockoutJS
When working with , there seem to be many common operations that you need to perform on your view model objects. Internally, Knockout has a number of utility functions used by the library itself, but many of these functions might actually be handy for anyone using the library.
I wanted to build a sample that highlights a few of my favorite utilities.
Handling data from the server
One of the first tasks that you typically encounter is converting data from the server to a suitable format for use in Knockout. Suppose, we are provided a JSON string from the server that was not automatically turned into a JavaScript object:
var JSONdataFromServer = '[{&name&:&Peach&,&category&:&Fruits&,&price&:1},{&name&:&Plum&,&category&:&Fruits&,&price&:0.75},{&name&:&Donut&,&category&:&Bread&,&price&:1.5},{&name&:&Milk&,&category&:&Dairy&,&price&:4.50}]';
Knockout has a utility function ko.utils.parseJson that will attempt to do a JSON.parse if it is available or fall back to evaluating it as a function string for older browsers.
So, we can turn our JSON string into an object like:
var dataFromServer = ko.utils.parseJson(JSONdataFromServer);
Now we have a JavaScript object, but in order to be useful in Knockout, we might need to convert some properties to observables and possibly add some computed observables.
One option for doing this is Knockout’s
By default, it will convert all arrays into observableArrays and all other properties into observables.
It also has hooks to control creation in more advanced scenarios. However, for fairly simple scenarios, it is easy enough to do the mapping yourself like:
function Item(name, category, price) {
this.name = ko.observable(name);
this.category = ko.observable(category);
this.price = ko.observable(price);
this.priceWithTax = ko.dependentObservable(function() {
return (this.price() * 1.05).toFixed(2);
//do some basic mapping (without mapping plugin)
var mappedData = ko.utils.arrayMap(dataFromServer, function(item) {
return new Item(item.name, item.category, item.price);
So, we have a constructor function for an Item, which creates our observables and adds a computed observable for showing the price with tax. We generate a mapped array of objects by using ko.utils.arrayMap, which executes a function for each item in an array and pushes the result of the function to a new array that is returned.
Dealing with arrays in your view model
Now we have an array of items that is ready for use in Knockout. When dealing with an array though, there seem to be several common scenarios where utility functions come in handy.
Looping through an array
Suppose we want to create a computed observable at the root view model level to track the grand total for all items. We will need to sum the priceWithTax value for all items. We could easily write a for loop to do this (or if we are using jQuery, $.each), but Knockout provides a utility function ko.utils.arrayForEach for this purpose.
We can use this function to get our total by doing something like:
viewModel.total = ko.computed(function() {
var total = 0;
ko.utils.arrayForEach(this.items(), function(item) {
var value = parseFloat(item.priceWithTax());
if (!isNaN(value)) {
total += value;
return total.toFixed(2);
}, viewModel);
Filtering an array
Next, say we want to allow a user to filter the list of items by name.
We could create a computed observable that returns the matching subset of the original array of items.
Knockout’s ko.utils.arrayFilter provides an implementation of this functionality that allows us to pass in an array and control which items are included based on the result of the function executed on each item.
For example, suppose we bind a textbox to a filter observable and use it to get our filtered items:
//filter the items using the filter text
viewModel.filteredItems = ko.computed(function() {
var filter = this.filter().toLowerCase();
if (!filter) {
return this.items();
return ko.utils.arrayFilter(this.items(), function(item) {
return ko.utils.stringStartsWith(item.name().toLowerCase(), filter);
}, viewModel);
We pass our array of items into ko.utils.arrayFilter and return true only when the item’s name starts with the value of the filter observable (ko.utils.stringStartsWith provides an easy way to do this). Now we can bind our display to filteredItems and it will react to changes in the filter textbox. We would most likely want the display to update on each keystroke, so on our input field we can specify the binding like:
note: ko.utils.stringStartsWith is not exported in the minified KO file`.
The code is simple enough though to replicate.
&p&Filter: &input data-bind=&value: filter, valueUpdate: 'afterkeydown'& /&&/p&
Searching for an item in the array
Besides being able to filter the display, let’s say that we also want to be able to enter a search term and highlight the first matching entry by name. Knockout provides ko.utils.arrayFirst that will execute a function against each item in our array and return the first item where the function evaluates to true. Similar to the filteredItems computed observable, we can create one that returns the first match from our search field:
//identify the first matching item by name
viewModel.firstMatch = ko.computed(function() {
var search = this.search().toLowerCase();
if (!search) {
return null;
return ko.utils.arrayFirst(this.filteredItems(), function(item) {
return ko.utils.stringStartsWith(item.name().toLowerCase(), search);
}, viewModel);
Now we can use viewModel.firstMatch in our template to compare it against the item ($data) that we are sending through our template and style the matching row appropriately.
Flattening an array
Suppose we needed an array that contains all of the categories currently being used in our items.
Knockout’s ko.utils.arrayMap that we used earlier is a nice way to take an array of objects and generate a flattened structure.
//get a list of used categories
viewModel.justCategories = ko.computed(function() {
var categories = ko.utils.arrayMap(this.items(), function(item) {
return item.category();
return categories.sort();
}, viewModel);
Our justCategories computed observable now contains an array of the used categories.
Getting just the unique values in an array
While we now have a list of categories in justCategories, what we might really want is a list of the unique categories represented in our items.
Knockout’s ko.utils.arrayGetDistinctValues takes in an array and returns an array that contains only the unique values.
//get a unique list of used categories
viewModel.uniqueCategories = ko.dependentObservable(function() {
return ko.utils.arrayGetDistinctValues(viewModel.justCategories()).sort();
}, viewModel);
Comparing two arrays
We have a list of the available categories and we have a list of the unique categories that are being used. Suppose that we want to provide a list of the categories that are missing from our data. Knockout’s pareArrays provides functionality to compare two arrays and indicate which items are different. For example:
//find any unused categories
viewModel.missingCategories = ko.dependentObservable(function() {
//find out the categories that are missing from uniqueNames
var differences = ko.utils.compareArrays(viewModel.categories, viewModel.uniqueCategories());
//return a flat list of differences
var results = [];
ko.utils.arrayForEach(differences, function(difference) {
if (difference.status === &deleted&) {
results.push(difference.value);
return results;
}, viewModel)
The result of pareArrays is an array that contains items with a status property (added, deleted, or retained) and a value property holding the original item.
Sending data back to the server
At some point, most applications will need to post data back to the server to persist changes to storage.
Our view model is likely not quite in a suitable format for use on the server.
Converting our view model using ko.toJS or ko.toJSON
I hesitate to call ko.toJS and ko.toJSON utilities, because they seem to be a necessity as soon as you need to package up some or all of your view model for transporting it back to the server. Usually a first attempt at doing this would involve calling something like JSON.stringify(viewModel). After seeing the result, you are immediately reminded that observables are actually functions and that JSON does not contain functions, so the observables are ignored by JSON serializers.
Luckily, Knockout includes these helper functions to facilitate transforming all of your observables and computed observables into normal properties on a JavaScript object.
ko.toJS – this function creates a copy of the object that you pass to it with all observables and computed observables converted into normal properties that are set to the current value.
ko.toJSON – this function first does ko.toJS on your object and then converts that object to a JSON string representation that is suitable for transferring back to the server.
Note: this uses the browser’s native JSON.stringify() function, which is not available in some older browsers.
One way to overcome this is by referencing a script from .
Removing properties from our converted array
We can use ko.toJS to turn our observables into a plain object, but we may need to do some additional tweaking before it is ready to send to the server. A common scenario is that your view model contains various computed observables for display that are not expected by your server-side code.
Again ko.utils.arrayMap is useful to trim the fat off of your objects:
var items = ko.toJS(this.items);
var mappedItems = ko.utils.arrayMap(items, function(item) {
delete item.priceWithTax;
return item;
Now our items are in a proper format for posting to our server.
Knockout contains a number of utility functions that are useful for manipulating your view model. These were the ones that I find most useful. Check out the Knockout
to see all of the available utility functions.
Here is a completed sample demonstrating these utility functions:
Posted by Ryan Niemeyer
Please enable JavaScript to view the
Copyright & 2015 - Ryan Niemeyer -
Powered by