Skip to main content

usama

User since Aug 5, 2023
2 Posts

Recent Posts

Daily: Find missing array value

Aug 5, 2023usama

1 like • 5 views

/*
Good morning! Here's your coding interview problem for today.
This problem was asked by Stripe.
Given an array of integers, find the first missing positive integer in linear time and constant space. In other words, find the lowest positive integer that does not exist in the array. The array can contain duplicates and negative numbers as well.
For example, the input [3, 4, -1, 1] should give 2. The input [1, 2, 0] should give 3.
You can modify the input array in-place.
*/
#include <iostream>
using namespace std;
int calcMissing(int* input, int size)
{
int sum = 0;
int n = 1; //add one to account for missing value
for(int i = 0; i < size; i++)
{
if(input[i] > 0)
{
sum += input[i];
n++;
}
}
//If no numbers higher than 0, answer is 1
if(sum == 0)
return 1;
return (n*(n+1)/2) - sum; //Formula is expectedSum - actualSum
/* expectedSum = n*(n+1)/2, the formula for sum(1, n) */
}
int main()
{
cout << calcMissing(new int[4]{3, 4, -1, 1}, 4) << endl;
cout << calcMissing(new int[3]{1, 2, 0}, 3) << endl;
//No positive numbers
cout << calcMissing(new int[1]{0}, 1) << endl;
}

Untitled

Aug 5, 2023usama

0 likes • 5 views

public class King {
fewf
}

Post Statistics

Posts

No Posts Found

It looks like usama has no public posts

Likes

Please Log In

You must be authenticated to view a user's likes

Shared

Please Log In

You must be authenticated to view a user's shared posts

Profile Privacy

Multi-Factor Authentication

Multi-Factor Authentication (MFA) is an authentication method that requires you to provide two or more verification factors to gain access to your account. In addition to username and password, MFA requires you to verify your email on every login, which decreases the likelihood of someone stealing your account.

Change Password

Forgot Password?

Identity Color

Changes the color of your profile icon and cursor highlight in the live code editor. You and other users will be able to view this change.

Delete Account

Deleting your account is permanent. All data associated with your account will be lost.